Q1. The Data structure used in standard implementation of Breadth First Search is?.
A. Stack.
B. Queue
C. Linked List.
D. None of the mentioned.
Answer= Stack
Q2. The Depth First Search traversal of a graph will result into?.
A. Linked List.
B. Tree.
C. Graph with back edges.
D. None of the mentioned.
Answer= Tree
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.
B. Breadth First Search.
C. Trim’s algorithm.
D. None of the mentioned.
Answer= Depth First Search
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.
Answer= 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.
Answer= When the graph is a Linked List
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.
Answer= Can be anything
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?.
A. linked list.
B. tree.
C. stack.
D. queue.
Answer= stack
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.
Answer= pre 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).
Answer= 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).
Answer= O(V)
Q12. Which of the following data structure is used to implement BFS?.
A. linked list.
B. tree.
C. stack.
D. queue.
Answer= 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.
Answer= Level-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.
Answer= O(V + E)
Q16. The Data structure used in standard implementation of Breadth First Search is?.
A. Stack.
B. Queue
C. Linked List.
D. None of the mentioned.
Answer= Queue
Q17. The Breadth First Search traversal of a graph will result into?.
A. Linked List.
B. Tree.
C. Graph with back edges.
D. All of the mentioned.
Answer= Tree
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.
B. Breadth First Search.
C. Trim’s algorithm.
D. None of the mentioned.
Answer= Breadth First Search
Q19. What can be the applications of Breadth First Search?.
A. Finding shortest path between two nodes.
B. Finding bipartiteness of a graph.
C. GPS navigation system.
D. All of the mentioned.
Answer= 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.
Answer= When the graph is a Linked List
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.
Answer= At most 1
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.
Answer= Judea Pearl
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.
Answer= Greedy BFS
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.
Answer= Heuristic Search
Q26. Which algorithm is used in graph traversal and path finding?.
A. A*.
B. C*.
C. D*.
D. E*.
Answer= A*
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.
Answer= 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*.
Answer= 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*.
Answer= Pure Heuristic Search
Q30. Who published the first A* search algorithm?.
A. Peter Hart.
B. Nils Nilsson.
C. Bertram Raphael.
D. Hans Berliner.
Answer= Hans Berliner
Q31. Who published the B* search algorithm?.
A. Peter Hart.
B. Nils Nilsson.
C. Bertram Raphael.
D. Hans Berliner.
Answer= Hans Berliner
Q32. Branch and bound is a __________.
A. problem solving technique.
B. data structure.
C. sorting algorithm.
D. type of tree.
Answer= problem solving technique
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.
D. linked list.
Answer= stack
Q35. Which data structure is used for implementing a FIFO branch and bound strategy?.
A. stack.
B. queue.
C. array.
D. linked list.
Answer= queue
Q36. Which data structure is most suitable for implementing best first branch and bound strategy?.
A. stack.
B. queue.
C. priority queue.
D. linked list.
Answer= 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.
Answer= FIFO 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.
Answer= LIFO 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.
Answer= false
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.
Answer= true
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.
Answer= 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.
Answer= FALSE