Virtual Labs

1. Which one of the following steps is incorrect when performing iterative DFS using a stack?

a: STEP 1: Start by putting any one of the graph's vertices on top of a stack; this acts as the source vertex of DFS. Explanation

Explanation

b: STEP 2: Take the top item of the stack and mark it as visited. Explanation

Explanation

c: STEP 3: Create a list of that vertex's adjacent vertices and add the ones that have already been visited to the top of the stack. Explanation

Explanation

d: STEP 4: Keep repeating the process until the stack is empty. Explanation

Explanation

2. What is the time complexity of DFS when

V

is the number of vertices and

E

is the number of edges, using an adjacency-list representation?

O(V^2)

Explanation

O(V + E)

Explanation

O(E^2)

Explanation

O(V \log V)

Explanation

3. Pick the incorrect option.

a: BFS may consume more memory than DFS for some graph structures. Explanation

Explanation

b: DFS goes deeper along a path before backtracking when necessary. Explanation

Explanation

c: BFS explores neighbors level by level before proceeding to vertices at greater depth. Explanation

Explanation

d: DFS uses a queue as its defining traversal structure. Explanation

Explanation

4. Which of the following are applications of DFS?

a: Topological sorting Explanation

Explanation

b: Cycle detection Explanation

Explanation

c: Finding connected components Explanation

Explanation

d: All of the above Explanation

Explanation

5. DFS can only be applied to trees and not to graphs.

a: True Explanation

Explanation

b: False Explanation

Explanation

6. Pick the incorrect option.

a: DFS uses exhaustive traversal along one path before exploring other options. Explanation

Explanation

b: DFS can be used to find the shortest path between two nodes in an unweighted graph. Explanation

Explanation

c: DFS can be implemented using a stack or recursion. Explanation

Explanation

d: DFS can be used in topological sorting. Explanation

Explanation

When we apply DFS on the above graph, which one of the following traversal orders is not possible?

a: 2,7,2,6,5,11,5,9,4 Explanation

Explanation

b: 2,7,5,2,6,9,5,11,4 Explanation

Explanation

c: 2,7,6,5,11,2,5,9,4 Explanation

Explanation

d: 2,5,9,4,7,2,6,5,11 Explanation

Explanation

8. Consider a connected graph with 6 vertices. If DFS starts from one vertex, how many vertices will be visited?

a: 1 Explanation

Explanation

b: 3 Explanation

Explanation

c: 5 Explanation

Explanation

d: 6 Explanation

Explanation

9. In an undirected graph, what does a DFS tree edge represent?

a: An edge that connects a newly discovered vertex to the vertex from which it was discovered. Explanation

Explanation

b: An edge that must connect two already visited vertices. Explanation

Explanation

c: An edge that is automatically removed after traversal. Explanation

Explanation

d: An edge that always connects vertices at the same depth. Explanation

Explanation

Depth First Search