# Graph Search in Data Structure and Algorithms MCQs

Q1. The Data structure used in standard implementation of Breadth First Search is?.

A.  Stack.

B.  Queue

D.  None of the mentioned.

Q2. The Depth First Search traversal of a graph will result into?.

B.  Tree.

C.  Graph with back edges.

D.  None of the mentioned.

Q3. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?.

A.  Depth First Search.

C.  Trim’s algorithm.

D.  None of the mentioned.

Q4. What can be the applications of Depth First Search?.

A.  For generating topological sort of a graph.

B.  For generating Strongly Connected Components of a directed graph.

C.  Detecting cycles in the graph.

D.  All of the mentioned.

Q5. When the Depth First Search of a graph is unique?.

A.  When the graph is a Binary Tree.

B.  When the graph is a Linked List.

C.  When the graph is a n-ary Tree.

D.  None of the mentioned.

Q6. Regarding implementation of Depth First Search using stacks, what is the maximum distance between two nodes present in the stack? (considering each edge length 1).

A.  Can be anything.

B. 0.

C.  At most 1.

D.  Insufficient Information.

Q7. In Depth First Search, how many times a node is visited?.

A.  Once.

B.  Twice.

C.  Equivalent to number of indegree of the node.

D.  None of the mentioned.

Answer=  Equivalent to number of indegree of the node

Q8. Which of the following data structure is used to implement DFS?.

B.  tree.

C.  stack.

D.  queue.

Q9. Which of the following traversal in a binary tree is similar to depth first traversal?.

A.  level order.

B.  post order.

C.  pre order.

D.  in order.

Q10. What will be the time complexity of the iterative depth first traversal code(V=no. of vertices E=no.of edges)?.

A.  O(V+E).

B.  O(V).

C.  O(E).

D.  O(V*E).

Q11. What is the space complexity of standard DFS(V: no. of vertices E: no. of edges)?.

A.  O(V+E).

B.  O(V).

C.  O(E).

D.  O(V*E).

Q12. Which of the following data structure is used to implement BFS?.

B.  tree.

C.  stack.

D.  queue.

Q13. Choose the incorrect statement about DFS and BFS from the following?.

A.  BFS is equivalent to level order traversal in trees.

B.  DFS is equivalent to post order traversal in trees.

C.  DFS and BFS code has the same time complexity.

D.  BFS is implemented using queue.

Answer=  DFS is equivalent to post order traversal in trees

Q14. Breadth First Search is equivalent to which of the traversal in the Binary Trees?.

A.  Pre-order Traversal.

B.  Post-order Traversal.

C.  Level-order Traversal.

D.  In-order Traversal.

Q15. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges).

A.  O(V + E).

B.  O(V).

C.  O(E).

D.  None of the mentioned.

Q16. The Data structure used in standard implementation of Breadth First Search is?.

A.  Stack.

B.  Queue

D.  None of the mentioned.

Q17. The Breadth First Search traversal of a graph will result into?.

B.  Tree.

C.  Graph with back edges.

D.  All of the mentioned.

Q18. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?.

A.  Depth First Search.

C.  Trim’s algorithm.

D.  None of the mentioned.

Q19. What can be the applications of Breadth First Search?.

A.  Finding shortest path between two nodes.

B.  Finding bipartiteness of a graph.

D.  All of the mentioned.

Q20. When the Breadth First Search of a graph is unique?.

A.  When the graph is a Binary Tree.

B.  When the graph is a Linked List.

C.  When the graph is a n-ary Tree.

D.  None of the mentioned.

Q21. Regarding implementation of Breadth First Search using queues, what is the maximum distance between two nodes present in the queue? (considering each edge length 1).

A.  Can be anything.

B. 0.

C.  At most 1.

D.  Insufficient Information.

Q22. In BFS, how many times a node is visited?.

A.  Once.

B.  Twice.

C.  equivalent to number of indegree of the node.

D.  None of the mentioned.

Answer=  equivalent to number of indegree of the node

Q23. Who described this Best First Search algorithm using heuristic evaluation rule?.

A.  Judea Pearl.

B.  Max Bezzel.

C.  Franz Nauck.

D.  Alan Turing.

Q24. Which type of best first search algorithm was used to predict the closeness of the end of path and its solution?.

A.  Greedy BFS.

B.  Divide and Conquer.

C.  Heuristic BFS.

D.  Combinatorial.

Q25. What is the other name of the greedy best first search?.

A.  Heuristic Search.

B.  Pure Heuristic Search.

C.  Combinatorial Search.

D.  Divide and Conquer Search.

Q26. Which algorithm is used in graph traversal and path finding?.

A.  A*.

B.  C*.

C.  D*.

D.  E*.

Q27. Which algorithm is used to find the least cost path from source node to destination node?.

A.  A* BFS.

B.  C* BFS.

C.  D* BFS.

D.  B* BFS.

Q28. Which of the following is an example of Best First Search algorithm?.

A.  A*.

B.  B*.

C.  C*.

D.  Both A* and B*.

Q29. Which of the following is the greedy best first search?.

A.  Pure Heuristic Search.

B.  A*.

C.  B*.

D.  Both A* and B*.

Q30. Who published the first A* search algorithm?.

A.  Peter Hart.

B.  Nils Nilsson.

C.  Bertram Raphael.

D.  Hans Berliner.

Q31. Who published the B* search algorithm?.

A.  Peter Hart.

B.  Nils Nilsson.

C.  Bertram Raphael.

D.  Hans Berliner.

Q32. Branch and bound is a __________.

A.  problem solving technique.

B.  data structure.

C.  sorting algorithm.

D.  type of tree.

Q33. Which of the following is not a branch and bound strategy to generate branches?.

A.  LIFO branch and bound.

B.  FIFO branch and bound.

C.  Lowest cost branch and bound.

D.  Highest cost branch and bound.

Answer=  Highest cost branch and bound

Q34. Which data structure is used for implementing a LIFO branch and bound strategy?.

A.  stack.

B.  queue.

C.  array.

Q35. Which data structure is used for implementing a FIFO branch and bound strategy?.

A.  stack.

B.  queue.

C.  array.

Q36. Which data structure is most suitable for implementing best first branch and bound strategy?.

A.  stack.

B.  queue.

C.  priority queue.

Q37. Which of the following branch and bound strategy leads to breadth first search?.

A.  LIFO branch and bound.

B.  FIFO branch and bound.

C.  Lowest cost branch and bound.

D.  Highest cost branch and bound.

Q38. Which of the following branch and bound strategy leads to depth first search?.

A.  LIFO branch and bound.

B.  FIFO branch and bound.

C.  Lowest cost branch and bound.

D.  Highest cost branch and bound.

Q39. Both FIFO branch and bound strategy and backtracking leads to depth first search..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q40. Both LIFO branch and bound strategy and backtracking leads to depth first search..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q41. Choose the correct statement from the following..

A.  branch and bound is more efficient than backtracking.

B.  branch and bound is not suitable where a greedy algorithm is not applicable.

C.  branch and bound divides a problem into at least 2 new restricted sub problems.

D.  backtracking divides a problem into at least 2 new restricted sub problems.

Answer=  branch and bound divides a problem into at least 2 new restricted sub problems

Q42. Which of the following can traverse the state space tree only in DFS manner?.

A.  branch and bound.

B.  dynamic programming.

C.  greedy algorithm.

D.  backtracking.

Q43. Which of the following is false in the case of a spanning tree of a graph G?.

A.  It is tree that spans G.

B.  It is a subgraph of the G.

C.  It includes every vertex of the G.

D.  It can be either cyclic or acyclic.

Answer=  It can be either cyclic or acyclic

Q44. Every graph has only one minimum spanning tree..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.