Virtual Labs

1. Let us consider

V

to be the total number of vertices and

E

to be the total number of edges in a tree. What is the time complexity of Breadth First Traversal in this tree?

O(E * V)

Explanation

O(V)

Explanation

O(E + V)

Explanation

O(E + E * V)

Explanation

2. What is the most appropriate data structure for Breadth First Traversal of a tree?

a: Linked List Explanation

Explanation

b: Queue Explanation

Explanation

c: Stack Explanation

Explanation

d: Array Explanation

Explanation

3. In Breadth First Traversal of a binary tree, when a node is removed from the queue, what is typically done next?

a: Its children are added to the queue Explanation

Explanation

b: The node is pushed onto a stack and ignored Explanation

Explanation

c: Only its parent is added to the queue Explanation

Explanation

d: The entire tree is traversed recursively before continuing Explanation

Explanation

4. Breadth First Traversal of a tree is also commonly called which of the following?

a: Postorder traversal Explanation

Explanation

b: Inorder traversal Explanation

Explanation

c: Level-order traversal Explanation

Explanation

d: Preorder traversal Explanation

Explanation

5. Which property of a queue makes it suitable for Breadth First Traversal?

a: Last-In-First-Out Explanation

Explanation

b: First-In-First-Out Explanation

Explanation

c: Random access Explanation

Explanation

d: Sorted insertion Explanation

Explanation

6. Consider a binary tree whose root is

A

, with children

B

and

C

. If

B

has children

D

and

E

, and

C

has children

F

and

G

, what is the Breadth First Traversal?

a: A, B, C, D, E, F, G Explanation

Explanation

b: A, D, B, E, C, F, G Explanation

Explanation

c: D, E, B, F, G, C, A Explanation

Explanation

d: A, B, D, E, C, F, G Explanation

Explanation

7. What is the maximum number of nodes stored in the queue at a particular point during Breadth First Traversal?

a: Always exactly one node Explanation

Explanation

b: Always equal to the height of the tree Explanation

Explanation

c: It can be proportional to the maximum width of the tree Explanation

Explanation

d: Always equal to the total number of nodes Explanation

Explanation

8. If a tree has

V

vertices and

E

edges, how many times is each vertex typically processed during a standard Breadth First Traversal?

a: Exactly once Explanation

Explanation

b: Exactly twice Explanation

Explanation

c: At least

V

times Explanation

Explanation

d: Exactly

E

times Explanation

Explanation

9. Suppose the root of a binary tree is at level

0

. Which nodes are processed before nodes at level

2

during Breadth First Traversal?

a: Only the root Explanation

Explanation

b: Only nodes at level

2

Explanation

c: Nodes at level

3

Explanation

d: Nodes at levels

0

and

1

Explanation

Tree Traversal