Depth First Search

1. Which one of the following data structures is used in DFS?

a: Heap Explanation

Explanation

b: Deque Explanation

Explanation

c: Priority Queue Explanation

Explanation

d: Stack Explanation

Explanation

2. What is backtracking in DFS?

a: Going to the parent or an earlier vertex when all reachable choices from the current path have been explored Explanation

Explanation

b: Going to the parent node whenever any child node has been visited Explanation

Explanation

c: Going to a sibling node immediately after visiting one child Explanation

Explanation

d: Going to a sibling node before visiting the current vertex Explanation

Explanation

3. What should DFS do when it encounters an already visited vertex?

a: Visit the vertex again immediately. Explanation

Explanation

b: Ignore that vertex for the current traversal step and continue with another unvisited option if available. Explanation

Explanation

c: Delete the vertex from the graph. Explanation

Explanation

d: Restart the entire DFS from the source. Explanation

Explanation

4. Which statement correctly describes recursive DFS?

a: It requires a queue to store all vertices before traversal begins. Explanation

Explanation

b: It visits only vertices having exactly one neighbor. Explanation

Explanation

c: It uses recursive function calls, with the call stack supporting the depth-first traversal and backtracking. Explanation

Explanation

d: It cannot be applied to graphs containing cycles. Explanation

Explanation

5. In DFS, why is a visited array or set maintained?

a: To store the numerical value of every edge Explanation

Explanation

b: To determine the weight of each vertex Explanation

Explanation

c: To sort vertices before traversal Explanation

Explanation

d: To prevent a vertex from being processed repeatedly Explanation

Explanation

6. Which of the following can DFS be used for?

a: Finding connected components Explanation

Explanation

b: Finding the average value of all vertex labels Explanation

Explanation

c: Changing all directed edges into undirected edges Explanation

Explanation

d: Automatically assigning numerical labels to all vertices Explanation

Explanation

7. Which of the following best describes the DFS traversal of a graph with cycles?

a: DFS must stop immediately when it encounters any edge that forms a cycle. Explanation

Explanation

b: DFS can continue correctly by using visited information to avoid repeatedly processing vertices. Explanation

Explanation

c: DFS cannot be applied to a cyclic graph. Explanation

Explanation

d: DFS removes every cyclic edge before continuing. Explanation

Explanation

8. Suppose DFS starts at vertex

A

and follows the path

A \rightarrow B \rightarrow C

. Vertex

C

has no unvisited adjacent vertex. What should happen next?

a: DFS deletes

C

. Explanation

Explanation

b: DFS starts again from

A

without returning through the current path. Explanation

Explanation

c: DFS backtracks from

C

to an earlier vertex such as

B

to look for another unvisited path. Explanation

Explanation

d: DFS converts the path into a queue. Explanation

Explanation

9. If an iterative DFS uses a stack, which vertex is processed first when several vertices are available on the stack?

a: The vertex most recently pushed onto the stack Explanation

Explanation

b: The vertex that was pushed first Explanation

Explanation

c: The vertex with the smallest label Explanation

Explanation

d: The vertex with the largest label Explanation

Explanation