Q.1 What does DFS stand for in graph algorithms?
Depth First Search
Depth Fast Scan
Data Flow Search
Directed Flow Strategy
Explanation - DFS stands for Depth First Search, a traversal algorithm that explores as far as possible along each branch before backtracking.
Correct answer is: Depth First Search
Q.2 Which data structure is typically used to implement DFS recursively?
Queue
Stack
Linked List
Tree
Explanation - DFS uses a stack. In recursive implementations, the system call stack is used implicitly.
Correct answer is: Stack
Q.3 DFS can be applied on which of the following?
Graphs only
Trees only
Both trees and graphs
Neither trees nor graphs
Explanation - DFS is applicable to both trees and graphs since trees are a subset of graphs.
Correct answer is: Both trees and graphs
Q.4 What is the worst-case time complexity of DFS for a graph with V vertices and E edges?
O(V)
O(E)
O(V + E)
O(V * E)
Explanation - DFS visits all vertices and edges once, hence the complexity is O(V + E).
Correct answer is: O(V + E)
Q.5 Which traversal is closely related to DFS?
Preorder Traversal
Inorder Traversal
Postorder Traversal
Level-order Traversal
Explanation - DFS on trees resembles preorder traversal, as nodes are visited before their children.
Correct answer is: Preorder Traversal
Q.6 Which of the following is TRUE about DFS?
DFS always finds the shortest path
DFS can be used for topological sorting
DFS uses a queue
DFS never detects cycles
Explanation - DFS is not guaranteed to find shortest paths, but it is used in topological sorting of DAGs.
Correct answer is: DFS can be used for topological sorting
Q.7 Which of the following is a typical application of DFS?
Finding shortest path in weighted graphs
Cycle detection
Dijkstra’s algorithm
Prim’s algorithm
Explanation - DFS is used to detect cycles in directed and undirected graphs.
Correct answer is: Cycle detection
Q.8 What happens if DFS is applied on a disconnected graph?
It traverses the entire graph
It traverses only the connected component
It crashes
It repeats nodes infinitely
Explanation - DFS from a starting node only visits nodes in the same connected component.
Correct answer is: It traverses only the connected component
Q.9 Which of the following traversal uses recursion more naturally?
BFS
DFS
Dijkstra
Kruskal
Explanation - DFS is naturally recursive, while BFS typically requires an explicit queue.
Correct answer is: DFS
Q.10 In DFS, what is the purpose of marking nodes as visited?
To count total nodes
To prevent infinite loops
To find shortest paths
To reduce memory usage
Explanation - Marking nodes as visited ensures DFS doesn’t revisit nodes endlessly, especially in cyclic graphs.
Correct answer is: To prevent infinite loops
Q.11 DFS is preferred over BFS when?
Graph is small
We need shortest path
Space is a concern
We need level order traversal
Explanation - DFS uses less memory compared to BFS, especially in sparse graphs.
Correct answer is: Space is a concern
Q.12 Which of the following uses DFS internally?
Topological sorting
Kruskal’s MST
Dijkstra’s shortest path
Prim’s MST
Explanation - Topological sorting of DAGs can be done using DFS postorder traversal.
Correct answer is: Topological sorting
Q.13 DFS traversal of a graph is similar to which tree traversal?
Preorder
Inorder
Postorder
Level-order
Explanation - DFS explores nodes first, like preorder traversal of trees.
Correct answer is: Preorder
Q.14 What is the space complexity of DFS using adjacency list?
O(V)
O(V + E)
O(E)
O(1)
Explanation - DFS requires O(V) space for visited array and recursion stack.
Correct answer is: O(V)
Q.15 DFS is not suitable for?
Cycle detection
Topological sorting
Shortest path finding
Connected components
Explanation - DFS does not guarantee shortest path, unlike BFS.
Correct answer is: Shortest path finding
Q.16 Which of the following indicates that a graph is cyclic in DFS?
Encountering an already visited node in same DFS path
Not visiting all nodes
Visiting all nodes
None
Explanation - In DFS, revisiting a node in the same path indicates a cycle.
Correct answer is: Encountering an already visited node in same DFS path
Q.17 In directed graphs, what does DFS help to detect?
Strongly connected components
Minimum spanning tree
Shortest path
Eulerian circuit
Explanation - DFS is used in algorithms like Kosaraju’s to find SCCs in directed graphs.
Correct answer is: Strongly connected components
Q.18 What happens if recursion depth exceeds system limit in DFS?
DFS restarts
Stack overflow error
Graph traversal completes normally
It converts to BFS
Explanation - Recursive DFS relies on system stack, which can overflow if the graph is deep.
Correct answer is: Stack overflow error
Q.19 Which color is used in DFS to indicate an unvisited node in CLRS convention?
White
Gray
Black
Red
Explanation - In CLRS, DFS colors nodes white (unvisited), gray (in-progress), and black (finished).
Correct answer is: White
Q.20 Which of these is FALSE about DFS?
DFS can be recursive
DFS uses stack
DFS always finds shortest path
DFS can detect cycles
Explanation - DFS does not guarantee shortest path. BFS is better for shortest paths in unweighted graphs.
Correct answer is: DFS always finds shortest path
Q.21 What traversal order is used in DFS for adjacency list?
Depends on vertex ordering
Always alphabetical
Always numerical
Random
Explanation - DFS order depends on how adjacency lists are stored and iterated.
Correct answer is: Depends on vertex ordering
Q.22 Which variant of DFS is used in backtracking problems?
Iterative DFS
Recursive DFS
Randomized DFS
Bidirectional DFS
Explanation - Backtracking problems rely on recursive DFS for exploring possibilities.
Correct answer is: Recursive DFS
Q.23 Which algorithm is based on DFS for solving 2-SAT problem?
Kosaraju’s algorithm
Kruskal’s algorithm
Prim’s algorithm
Bellman-Ford algorithm
Explanation - Kosaraju’s algorithm, based on DFS, is used for finding SCCs in directed graphs, crucial for solving 2-SAT.
Correct answer is: Kosaraju’s algorithm
Q.24 DFS tree edges are classified into?
Tree, Back, Forward, Cross
Parent, Child, Sibling
Incoming, Outgoing
Visited, Unvisited
Explanation - In DFS, edges are classified as tree, back, forward, and cross based on discovery/finish times.
Correct answer is: Tree, Back, Forward, Cross
Q.25 Which function is essential in recursive DFS implementation?
DFSUtil()
enqueue()
relax()
union()
Explanation - Recursive DFS often uses a helper function (commonly named DFSUtil or dfs) for traversal.
Correct answer is: DFSUtil()