CS607P Quiz 3 by VU Topper RM

Time Complexity of Breadth First Search is ____________ . A. O(V*E) B. O(V) C. O(E)

D. O(V+E)

Depth First Search (DFS) explores nodes by: A. Visiting nodes in random order

B. Visiting as deep as possible along each branch before backtracking

C. Visiting all neighbouring nodes before going deeper D. Visiting nodes level by level

If DFS starts from A and visits C before B, what is the DFS traversal order? Graph (Adjacency List): A → B, C B → C C → (no outgoing edges) A. A, B, C

B. A, C, B

C. A, C D. A, B

On the given graph, if we perform DFS starting from node A. Which of the following could be a valid DFS traversal order? Graph (Adjacency List): A → B, C B → (no outgoing edges) C → (no outgoing edges)

A. A, B, C

B. C, A, B C. B, C, A D. C, B, A largest value of height will be at the _________ priority to be picked from queue Q. A. Zero

B. Maximum

C. Minimum D. Average

In BFS, each vertex is visited: A. Once for each adjacent edge

B. Exactly once

C. Twice D. Until a cycle is detected

In BFS, which nodes are visited first?

1. Deepest nodes first
2. Random nodes
3. Nodes with the highest value
4. Nodes closest to the start node

Correct answer: Nodes closest to the start node

______ data structure is used in the implementation of Breadth First Search. A. Stack B. Linked List

C. Queue

D. Tree

Which data structure is used to implement DFS iteratively?

1. Heap
2. Stack
3. List
4. Queue

Correct answer: Stack

In BFS, what condition is used to add a node to the queue?

1. If it has the smallest value
2. If it has not been visited yet
3. If it has a parent node
4. If its degree is even

Correct answer: If it has not been visited yet

If DFS starts from A and visits B before C, what is the DFS traversal order?

A → B, C B → D C → D D → (no outgoing edges)

A, D, B, C A, C, D, B

A, B, D, C

A, B, C, D

On the given graph, if DFS starts from A and visits C first, what is the traversal order?

A → B, C B → C C → (no outgoing edges)

B, A, C