Data Structures Quiz: Depth-First Search

Which data structure is most commonly used to implement a non-recursive Depth-First Search?

• Queue

• Stack

• Linked List

• Hash Table

In a Depth-First Search, how does the algorithm decide which node to visit next?

• It visits all neighbors of the current node before moving deeper.

• It follows a single path as far as possible before backtracking.

• It visits nodes in order of their numerical value.

• It randomly selects a connected node.

When implementing DFS recursively, what handles the 'Stack' functionality?

• The Operating System's Heap memory

• A global array

• The Program Call Stack

• A Pointer variable

What is the standard Time Complexity of DFS for a graph with $V$ vertices and $E$ edges?

• $O(V)$

• $O(E)$

• $O(V + E)$

• $O(V^2)$

Which of the following is a primary use case for Depth-First Search?

• Finding the shortest path in an unweighted graph

• Solving puzzles like Mazes or Sudoku

• Level-order traversal of a tree

• Managing a printer queue

In a graph traversal, what is the purpose of a 'Visited' list/set?

• To store the final path

• To prevent infinite loops in graphs with cycles

• To sort the nodes alphabetically

• To count the number of edges

If a DFS reaches a node with no unvisited neighbors, what is the next step?

• The algorithm terminates

• It restarts from the root node

• It backtracks to the previous node

• It skips to the next numerical node

Which of these is NOT a valid DFS traversal order for a Tree?

• Pre-order

• In-order

• Post-order

• Level-order

In a directed graph, DFS can be used to detect cycles. If you encounter a node that is currently 'in progress' (on the stack), what does this indicate?

• A back-edge (cycle detected)

• A dead end

• The shortest path

• A disconnected component

Compared to Breadth-First Search (BFS), DFS generally uses:

• More memory for wide trees

• Less memory for deep, narrow trees

• Less memory for wide, shallow trees

• The same amount of memory regardless of shape