Data Structures Graphs

Question 1

Which data structure is used to implement Breadth-First Search (BFS) in a graph?

Accepted Answer

Queue

Answer

BFS uses a queue to visit nodes level by level, ensuring FIFO order of exploration.

Question 2

In an adjacency matrix representation of a graph with V vertices, what is the space complexity?

Accepted Answer

O(V²)

Answer

An adjacency matrix stores a V×V grid of values, requiring O(V²) space regardless of the number of edges.

Question 3

What is a directed acyclic graph (DAG)?

Accepted Answer

A directed graph with no cycles

Answer

A DAG is a directed graph that contains no directed cycles, making topological sorting possible.

Question 4

Which of the following best describes a weighted graph?

Accepted Answer

A graph where edges have associated numeric values

Answer

In a weighted graph, each edge carries a numeric value (weight) representing cost, distance, or capacity.

Question 5

What is the degree of a vertex in an undirected graph?

Accepted Answer

The number of edges incident to that vertex

Answer

The degree of a vertex is the count of edges connected to it; self-loops are typically counted twice.

Data Structures Practice Test