Graphs Interview Questions Part 5

36. A structure for representing a graph in which the presence of arcs between nodes is is indicated by an entry in a matrix is ________
a. Breadth-first search
b. Depth-first search
c. Adjacency matrix
d. Adjacency list
Ans. c

37. A structure for representing a graph in which the arcs are stored as lists of connections between nodes is ________
a. Breadth-first search
b. Depth-first search
c. Adjacency matrix
d. Adjacency list
Ans. d

38. The amount of space required to store an adjacency-matrix is ____ where V is a vertex set whose elements are vertices.
a. O(V)
b. O(V+E)
c. O(V²)
d. O(V*E)
Ans. c

39. Any edge in an adjacency matrix representation can be accessed,added or removed in ______ time.
a. O(V)
b. O(1)
c. O(E)
d. O(V²)
Ans. b

40. For sparse graphs,the amount of memory required to store an adjacency list is ______
a. O(V)
b. O(V²)
c. O(V+E)
d. O(V*E)
Ans. c

41. A technique that picks the next adjacent unvisited vertex until reaching a vertex that has no unvisited adjacent vertices is ________
a. Breadth-first search
b. Depth-first search
c. Adjacency matrix
d. Adjacency list
Ans. b

42. Consider the graph represented by the following adjacency list:
1: 2—3—6
2: 5—1—3
3: 2—1—7—5—6
4: 5—7
5: 2—4—3—6
6: 3—5—1
7: 3—4
Perform a Breadth First Search in the graph starting from node 1 and processing the
edges adjacent to a node in the order they appear in the adjacency list.
What is the order in which the nodes are visited?
a) 1,2,3,6,4,7,5
b) 1,2,3,6,7,5,4
c) 1,2,3,6,5,4,7
d) 1,2,3,6,5,7,4
e) 1,2,3,6,7,4,5
Ans. d




44. If you perform a Depth First Search in a binary tree, what traversal will you obtain?
a) pre-order
b) in-order
c) post-order
d) Eulerian
Ans. a

45. Given a graph G with n nodes, you want to find the node that has maximum degree.
What would be the complexity using an adjacency matrix?
a) O(1) b) O(log n) c) O(n) d) O(n log n) e) O(n2)
Ans. e

46. Given a graph G with n nodes and m edges, you want to find all the nodes with
degree 5. What would be the complexity using an adjacency list (where the degree of
each node is not stored)?
a) O(n) b) O(log m) c) O(log n) d) O(m) e) O(n logn )
Ans. d

47. Which of the following statements is incorrect?
a) A tree with n nodes has n-1 edges
b) Dijkstra does not work if some weights are negative
c) BSF finds whether a graph is connected
d) All nodes in a graph must have degree at least 1
Ans. d

48.Depth first search of a graph is
i.recursive
ii.can be parallelized
a.only I b.only ii c.i and ii d.neither I nor ii
Ans:a
Some problems have no parallel algorithms, and are called inherently serial problems. Those problems cannot be solved faster by employing more processors. One such example is depth-first search of a graph, which happens to be recursive, but can not be parallelized