# Graph Data Structure MCQ

1. Depth 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

In-Depth First Search, we explore all the nodes aggressively to one path and then backtrack to the node. Hence, it is equivalent to the pre-order traversal of a Binary Tree.

2. What Time Complexity of DFS is? (V – number of vertices, E – number of edges)

a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)

The Depth First Search explores every node once and every edge once (in the worst case), so its time complexity is O(V + E).

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

a) Stack
b) Queue
d) Tree

The Depth First Search is implemented using recursion. So, the stack can be used as a data structure to implement a depth-first search.

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

b) Tree
c) Graph with back edges
d) Array

The Depth First Search will make a graph that doesn’t have back edges (a tree) which is known as Depth First Tree.

5. 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 explores another vertex from the same vertex. What algorithm he should use?

a) Depth First Search
c) Trim’s algorithm
d) Kruskal’s Algorithm

This is the definition of the Depth First Search. Exploring a node, then aggressively finding nodes till it is not able to find any node.

6. Which of the following is not an application of Depth First Search?

a) For generating a topological sort of a graph
b) For generating Strongly Connected Components of a directed graph
c) Detecting cycles in the graph
d) Peer-to-Peer Networks

Depth First Search is used in the Generation of topological sorting, Strongly Connected Components of a directed graph, and to detect cycles in the graph. Breadth First Search is used in peer-to-peer networks to find all neighborhood nodes.

7. 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 an n-ary Tree
d) When the graph is a ternary Tree

When Every node will have one successor then the Depth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding the 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

Regarding the implementation of Depth First Search using stacks, the maximum distance between two nodes present in the stack Can be anything.

In the stack, at a time, there can be nodes that can differ on many levels. So, it can be the maximum distance between two nodes in the graph.

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

a) Once
b) Twice
c) Equivalent to the number of indegree of the node
d) Thrice

In-Depth First Search, we have to see whether the node is visited or not by its ancestor. If it is visited, we won’t let it enter the stack.

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

b) tree
c) stack
d) queue

Stack is used in the standard implementation of depth-first search. It is used to store the elements which are to be explored.

2. 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

In DFS we keep on exploring as far as possible along each branch before backtracking. It terminates when all nodes are visited. So it is similar to pre-order traversal in a binary tree.

4. 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)

As the time required to traverse a full graph is V+E so its worst-case time complexity becomes O(V+E). The time complexity of iterative and recursive DFS are the same.

8. 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)

In the worst case, the space complexity of DFS will be O(V) in the case when all the vertices are stored in the stack. This space complexity excludes the space required to store the graph.

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

b) tree
c) stack
d) queue

The queue is used in the standard implementation of breadth-first search. It is used to store the vertices according to the coding algorithm.

10. 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

DFS is equivalent to pre-order traversal in trees, not post-order traversal. It is so because in DFS we keep on exploring as far as possible along each branch before backtracking. So it should be equivalent to pre-order traversal.

1. 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

Breadth First Search is equivalent to Level-order Traversal in the Binary Trees.

The Breadth First Search Algorithm searches the nodes based on level. It takes a node (level 0), explores its neighbors (level 1), and so on.

2. 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) O(V*E)

The Breadth First Search explores every node once and every edge once (in the worst case), so its time complexity is O(V + E).

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

a) Stack
b) Queue
d) Tree

The Breadth First Search explores every node once and puts that node in the queue and then it takes out nodes from the queue and explores its neighbors.

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

b) Tree
c) Graph with back edges
d) Arrays

The Breadth First Search will make a graph that doesn’t have back edges (a tree) which are known as Breadth First Tree.

5. 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) Kruskal’s algorithm

This is the definition of the Breadth First Search. Exploring a node, then its neighbors, and so on.

6. Which of the following is not an application of Breadth First Search?

a) Finding the shortest path between two nodes
b) Finding bipartiteness of a graph
d) Path Finding

Breadth First Search can be applied to Bipartite a graph, to find the shortest path between two nodes, in GPS Navigation. In Path finding, Depth First Search is used.

7. 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 an n-ary Tree
d) When the graph is a Ternary Tree

When Every node will have one successor then the Breadth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding the 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

In the queue, at a time, only those nodes will be there a whose difference among levels is 1. Same as level order traversal of the tree.

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

a) Once
b) Twice
c) Equivalent to the number of indegree of the node
d) Thrice

In Breadth First Search, we have to see whether the node is visited or not by its ancestor. If it is visited, we won’t let it enter the queue.

1. Is Best First Search a searching algorithm used in graphs?

a) True
b) False

Best First Search is a searching algorithm used in graphs. It explores it by choosing a node by heuristic evaluation rule. It is used in solving searching for related problems.

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

a) Judea Pearl
b) Max Bezzel
c) Franz Nauck
d) Alan Turing

The best first search algorithm using a heuristic evaluation rule or function was proposed by an Israeli – American computer scientist and philosopher Judea Pearl.

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

a) Greedy BFS
b) Divide and Conquer
c) Heuristic BFS
d) Combinatorial

The greedy best-first search algorithm was used to predict the closeness of the end of the path and its solution by some computer scientists.

4. 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

The greedy best-first search algorithm was used to predict the closeness of the end of the path and its solution by some computer scientists. It is also known as Pure Heuristic Search.

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

a) A*
b) C*
c) D*
d) E*

In computer science, the A* algorithm is used in graph traversal and path finding. It is a process of node finding in between a path. It is an example of the best first search.

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

a) A* BFS
b) C* BFS
c) D* BFS
d) B* BFS

In computer science, the B* algorithm is used to find the least cost path between the source node and the destination node. It is an example of the best first search.

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

a) A*
b) B*
c) C*
d) Both A* and B*

In computer science, the A* algorithm is used in graph traversal and path finding. It is a process of node finding in between a path. B* algorithm is used to find the least cost path between the source node and the destination node.

8. Which of the following is the greedy best-first search?

a) Pure Heuristic Search
b) A*
c) B*
d) Both A* and B*

Pure Heuristic Search is also called greedy best-first search while A* and B* search algorithms are not greedy best-first search.

9. Which of the following scientists didn’t publish an A* algorithm?

a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner

Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first published the A* search algorithm which uses heuristics for better performance. Hans Berliner published B* algorithm.

10. Who published the B* search algorithm?

a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner

Hans Berliner was a Computer Science professor who first published the B* search algorithm in 1979. While Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first published the A* search algorithm which uses heuristics for better performance.

1. Branch and bound is a __________

a) problem-solving technique
b) data structure
c) sorting algorithm
d) type of tree

Branch and bound is a problem-solving technique generally used for solving combinatorial optimization problems. Branch and bound help in solving them faster.

2. 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

LIFO, FIFO, and Lowest cost branches and bound are different strategies to generate branches. Lowest cost branch and bound helps us find the lowest cost path.

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

a) stack
b) queue
c) array

Stack is the data structure used for implementing the LIFO branch and bound strategy. This leads to a depth-first search as every branch is explored until a leaf node is discovered.

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

a) stack
b) queue
c) array

The queue is the data structure used for implementing the FIFO branch and bound strategy. This leads to a breadth-first search as every branch at depth is explored first before moving to the nodes at greater depth.

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

a) stack
b) queue
c) priority queue

Priority Queue is the data structure used for implementing the best first branch and bound strategy. Dijkstra’s algorithm is an example of the best first search algorithm.

6. Which of the following branch and bound strategies leads to a 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

LIFO, FIFO, and Lowest cost branches and bound are different strategies to generate branches. FIFO branch and bound leads to breadth-first search.

7. Which of the following branch and bound strategies leads to a 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

LIFO, FIFO, and Lowest cost branches and bound are different strategies to generate branches. LIFO branch and bound leads to depth-first search.

8. Both FIFO branch and bound strategy and backtracking lead to depth-first search.

a) true
b) false

9. Both LIFO branch and bound strategy and backtracking lead to depth-first search.

a) true
b) false

Both backtracking, as well as branch and bound, are problem-solving algorithms. Both LIFO branch and bound strategy and backtracking lead to depth-first search.

10. Choose the correct statement from the following about branch and bound.

a) branch and bound is more efficient than backtracking
b) branch and bound are not suitable where a greedy algorithm is not applicable
c) branch and bound divide a problem into at least 2 new restricted subproblems
d) backtracking divides a problem into at least 2 new restricted subproblems

Both backtracking, as well as branch and bound, are problem-solving algorithms. Branch and bound is less efficient than backtracking. Branch and bound divide a problem into at least 2 new restricted sub-problems.

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

a) branch and bound
b) dynamic programming
c) greedy algorithm
d) backtracking