Graphs Interview Questions Part 4

23. For the following graph, using breadth first search, which of the following elements are present at level 3

a.8,6 b.4,5 c.8,7,6 d.2,3
Ans:a
24. For the following graph, using breadth first search, which of the following elements are present at level 4

a.8,7,6 b.4,5 c.8,6 d.7
Ans:d

25. Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree.(T/F)
Ans:True
26.Choose the right statement from the following
a.Depth first search is closely related to traveling salesman problem
b. Breadth first search is closely related to traveling salesman problem
c. Breadth first search can be thought of as being like Dijkstra's algorithm for shortest paths
d. Depth first search can be thought of as being like Dijkstra's algorithm for shortest paths
Ans:a,c
27. Depth First Search is a generalization of the ________.
a.Inorder traversal
bPreorder traversal
c.Postorder traversal
d.none
Ans:b
28. For a graph with n nodes to be Cyclic, the minimum number of edges required are________.
a.n/2
b.n+1
c.n-1
d.n
Ans:d
29. For a Graph with v nodes and e edges, the running time of DFS is given by ________.
a.O(|V| + |E|)
b. O(|E|)
c. O(|V| )
d. O(|V| log |E|)
Ans:a
30. Breadth First Search algorithm can be used in Prim's MST algorithm. (T/F)
Ans:True
31. Breadth First Search algorithm cannot be used in Dijkstra’s single source shortest path algorithm. (T/F)
Ans:False

32. A graph with V vertices and E edges can be represented with an adjacency matrix using O(V2) space. (T/F)
true.

33. Consider the following pseudo code.
void PQR(Vertex v)
{ v.visited = true ;
For each w adjacent to v
if (!w.visited)
PQR(w); }
Which of the following is/are it intended to do?
a. Finding the adjacency matrix
b. Depth first search
c. Finding the path matrix
d. Breadth first search
e. Calculating the shortest path
Ans. Depth first search
34. Depth first search is a generalization of
a. Inorder traversal
b. Preorder traversal
c. Postorder traversal
d. none of the above
Ans. b

35. Traversing a graph by visiting all the nodes attached directly to a starting node first is called ___________
a. Depth-first search
b. Breadth-first search
c. Adjacency list
d. Adjacency matrix
Ans. b