What does DFS stand for in graph theory?
A) Depth First Search
B) Depth Factor Search
C) Depth Function Search
D) Depth Following Search
Answer: A) Depth First Search
Which data structure is primarily used in DFS?
A) Queue
B) Stack
C) Array
D) Linked list
Answer: B) Stack
What does BFS stand for in graph theory?
A) Best First Search
B) Breadth First Search
C) Balanced First Search
D) Broad First Search
Answer: B) Breadth First Search
Which data structure is primarily used in BFS?
A) Stack
B) Queue
C) Array
D) Linked list
Answer: B) Queue
What is the primary use of DFS?
A) Finding the shortest path
B) Traversing all vertices of a graph
C) Finding connected components
D) Searching for a specific vertex
Answer: B) Traversing all vertices of a graph
In which traversal method is the root node processed before its children?
A) BFS
B) DFS
C) Both BFS and DFS
D) Neither BFS nor DFS
Answer: B) DFS
Which traversal method guarantees the shortest path in an unweighted graph?
A) DFS
B) BFS
C) Both DFS and BFS
D) Neither DFS nor BFS
Answer: B) BFS
What is a key characteristic of BFS?
A) It explores all neighbors before going deeper
B) It uses a stack for exploration
C) It can get stuck in cycles
D) It always finds the longest path
Answer: A) It explores all neighbors before going deeper
In which traversal method is backtracking often used?
A) BFS
B) DFS
C) Both BFS and DFS
D) Neither BFS nor DFS
Answer: B) DFS
How does BFS handle cycles in a graph?
A) It ignores cycles
B) It gets stuck in an infinite loop
C) It marks visited nodes
D) It does not work with cycles
Answer: C) It marks visited nodes
What is the time complexity of BFS on a graph with V vertices and E edges?
A) O(V)
B) O(E)
C) O(V + E)
D) O(V * E)
Answer: C) O(V + E)
What is the time complexity of DFS on a graph with V vertices and E edges?
A) O(V)
B) O(E)
C) O(V + E)
D) O(V * E)
Answer: C) O(V + E)
Which traversal method is more memory-efficient for wide graphs?
A) DFS
B) BFS
C) Both have the same efficiency
D) None of the above
Answer: A) DFS
What is the space complexity of BFS?
A) O(V)
B) O(E)
C) O(V + E)
D) O(1)
Answer: A) O(V)
Which algorithm can be implemented using DFS?
A) Topological sorting
B) Prim’s algorithm
C) Dijkstra’s algorithm
D) Kruskal’s algorithm
Answer: A) Topological sorting
Which algorithm can be implemented using BFS?
A) Finding connected components
B) Topological sorting
C) Shortest path in unweighted graphs
D) Minimum spanning tree
Answer: C) Shortest path in unweighted graphs
What is the initial step in a BFS traversal?
A) Mark all nodes as unvisited
B) Push the starting node onto the stack
C) Enqueue the starting node
D) Start from the deepest node
Answer: C) Enqueue the starting node
What is the initial step in a DFS traversal?
A) Mark all nodes as unvisited
B) Push the starting node onto the queue
C) Enqueue the starting node
D) Start from the root node
Answer: A) Mark all nodes as unvisited
In DFS, what happens when a node has no unvisited neighbors?
A) It stops traversing
B) It backtracks to the last visited node
C) It enqueues all neighbors
D) It visits all nodes in the graph
Answer: B) It backtracks to the last visited node
What is a possible output of BFS on a tree structure?
A) Left-to-right traversal
B) Top-to-bottom traversal
C) Random order
D) Depth-based traversal
Answer: B) Top-to-bottom traversal
Which of the following is true about DFS?
A) It explores all nodes at the present depth
B) It visits nodes in a depth-wise manner
C) It is guaranteed to find the shortest path
D) It cannot be implemented recursively
Answer: B) It visits nodes in a depth-wise manner
What happens if the graph is disconnected in BFS?
A) It traverses all components
B) It only visits the starting component
C) It fails to complete
D) It visits all nodes randomly
Answer: B) It only visits the starting component
What happens if the graph is disconnected in DFS?
A) It only visits the starting component
B) It traverses all components
C) It fails to complete
D) It visits all nodes randomly
Answer: B) It traverses all components
Which traversal is better suited for searching a specific value in a graph?
A) BFS
B) DFS
C) Both are equally effective
D) Neither is effective
Answer: C) Both are equally effective
What can DFS be used to detect in a graph?
A) Cycles
B) Shortest paths
C) Connected components
D) All of the above
Answer: D) All of the above
Which traversal method is more likely to get stuck in infinite loops without proper checks?
A) BFS
B) DFS
C) Both are equally likely
D) Neither is likely
Answer: B) DFS
What is the worst-case time complexity of DFS for a binary tree with n nodes?
A) O(log n)
B) O(n)
C) O(n^2)
D) O(1)
Answer: B) O(n)
Which traversal can be performed using a simple recursive function?
A) BFS
B) DFS
C) Both BFS and DFS
D) Neither BFS nor DFS
Answer: B) DFS
What is the main advantage of using BFS over DFS?
A) Simplicity of implementation
B) Guarantees shortest path in unweighted graphs
C) Lower time complexity
D) Lower space complexity
Answer: B) Guarantees shortest path in unweighted graphs
What is the main disadvantage of using BFS?
A) Requires more memory
B) Cannot find shortest paths
C) Slower than DFS
D) More complex implementation
Answer: A) Requires more memory
How can BFS be modified to handle weighted graphs?
A) By using a priority queue
B) By converting to DFS
C) By adding extra nodes
D) It cannot be modified
Answer: A) By using a priority queue
In a binary tree, what is the order of traversal for DFS?
A) Pre-order, In-order, Post-order
B) Level-order
C) Breadth-first
D) Depth-first
Answer: A) Pre-order, In-order, Post-order
Which algorithm is based on BFS for finding the shortest path in weighted graphs?
A) Bellman-Ford algorithm
B) Dijkstra’s algorithm
C) Floyd-Warshall algorithm
D) Prim’s algorithm
Answer: B) Dijkstra’s algorithm
What is the role of a visited array in DFS?
A) To track the depth of nodes
B) To prevent revisiting nodes
C) To store node values
D) To maintain node order
Answer: B) To prevent revisiting nodes
Which traversal method is typically faster for finding a path in a maze?
A) BFS
B) DFS
C) Both are equally fast
D) Neither is effective
Answer: A) BFS
What is a characteristic of a depth-first traversal?
A) It uses less memory
B) It may not find the shortest path
C) It is faster than BFS
D) It visits nodes in a breadth-wise manner
Answer: B) It may not find the shortest path
What is the iterative implementation of DFS based on?
A) Queue
B) Stack
C) Recursion
D) Priority queue
Answer: B) Stack
In a complete binary tree, which traversal methods will visit nodes in the same order?
A) DFS and BFS
B) Pre-order and In-order
C) Post-order and In-order
D) Both BFS and DFS will yield different orders
Answer: D) Both BFS and DFS will yield different orders
Which traversal is more suitable for finding the maximum depth of a tree?
A) BFS
B) DFS
C) Both are equally suitable
D) None of the above
Answer: B) DFS
What is one drawback of using BFS?
A) It may miss some nodes
B) It uses too much memory
C) It cannot find paths
D) It is not intuitive
Answer: B) It uses too much memory
Which algorithm is commonly used in graph coloring problems?
A) DFS
B) BFS
C) Both can be used
D) Neither can be used
Answer: A) DFS
Which traversal is less likely to produce a deep recursion stack?
A) DFS
B) BFS
C) Both have the same likelihood
D) Neither is a factor
Answer: B) BFS
What is the common approach to implement BFS?
A) Using recursion
B) Using a priority queue
C) Using a queue
D) Using a stack
Answer: C) Using a queue
In DFS, what does the term “backtracking” refer to?
A) Revisiting nodes
B) Moving to a parent node after reaching a leaf
C) Skipping nodes
D) Starting the traversal again
Answer: B) Moving to a parent node after reaching a leaf
Basic Concepts
Non-Linear Data Structures MCQs
Sorting and Searching Algorithms MCQs
- Data Structures MCQs 1
- Data Structures MCQs 2
- Data Structures MCQs 3
- Data Structures MCQs 4
- Data Structures MCQs 5
- Stacks Solved MCQs
- Queues MCQs
- pointer mcqs
- Array MCQs