Virtual Labs

1. Which one of the following is an application of a directed graph?

a: Mobile communication graph Explanation

Explanation

b: Water network graph Explanation

Explanation

c: Scheduling courses with prerequisites Explanation

Explanation

d: Graph of friends Explanation

Explanation

2. If

m

and

n

represent the number of vertices and edges respectively, which one of the following combinations cannot be true for a graph?

m > 0

and

n > 0

Explanation

m > 0

and

n = 0

Explanation

m = 0

and

n > 0

Explanation

m = 10000

and

n = 1

Explanation

3. Which data structure can be used to represent a graph using an adjacency matrix and provides random access to its entries?

a: Linked List Explanation

Explanation

b: Tree Explanation

Explanation

c: Array Explanation

Explanation

d: Graph Explanation

Explanation

4. When performing DFS on a directed graph, how does the traversal move from a vertex?

a: It can move along any edge regardless of its direction. Explanation

Explanation

b: It always moves to the vertex with the smallest label. Explanation

Explanation

c: It always moves to the vertex with the largest label. Explanation

Explanation

d: It follows the explicitly directed edges from the current vertex. Explanation

Explanation

5. Which one of the following is an application of a directed graph?

a: Scheduling courses with prerequisites Explanation

Explanation

b: Data broadcasting from parent to child nodes Explanation

Explanation

c: Representing parent-child relationships in a family tree Explanation

Explanation

d: All of the above Explanation

Explanation

6. What is the main purpose of marking a vertex as visited during DFS?

a: To ensure that the vertex is processed at most once during the traversal. Explanation

Explanation

b: To increase the number of edges in the graph. Explanation

Explanation

c: To change a directed graph into an undirected graph. Explanation

Explanation

d: To guarantee that the vertex has no adjacent vertices. Explanation

Explanation

7. Which statement best describes the order in which DFS explores a graph?

a: It visits all vertices at the same depth before moving deeper. Explanation

Explanation

b: It explores as far as possible along a path before backtracking to explore another path. Explanation

Explanation

c: It always visits vertices in increasing numerical order. Explanation

Explanation

d: It always visits vertices in decreasing numerical order. Explanation

Explanation

8. For a graph represented using an adjacency list, what is the time complexity of DFS in terms of

V

, the number of vertices, and

E

, the number of edges?

O(V)

Explanation

O(E)

Explanation

O(V^2)

Explanation

O(V + E)

Explanation

9. Consider a connected undirected graph with

V

vertices. During a DFS traversal, how many tree edges are required to first reach all vertices?

V - 1

Explanation

V

Explanation

2V

Explanation

V + 1

Explanation

Depth First Search