Data Structures Graphs

Question 1

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

Accepted Answer

Queue

Answer

Stack

Answer

Priority Queue

Answer

Deque

Question 2

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

Accepted Answer

O(V²)

Answer

O(V)

Answer

O(E)

Answer

O(V + E)

Question 3

What is a directed acyclic graph (DAG)?

Accepted Answer

A directed graph with no cycles

Answer

A graph with no vertices

Answer

A graph where all edges are bidirectional

Answer

A graph where every vertex has equal degree

Question 4

Which of the following best describes a weighted graph?

Accepted Answer

A graph where edges have associated numeric values

Answer

A graph where each vertex has a numeric label

Answer

A graph with exactly as many edges as vertices

Answer

A graph where every vertex is connected to every other vertex

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 number of vertices in the graph

Answer

The shortest path from that vertex to all others

Answer

The number of vertices adjacent to it minus one

Question 6

Which graph representation is more space-efficient for sparse graphs?

Accepted Answer

Adjacency list

Answer

Adjacency matrix

Answer

Incidence matrix

Answer

Edge matrix

Question 7

What is the time complexity of Depth-First Search (DFS) on a graph represented as an adjacency list?

Accepted Answer

O(V + E)

Answer

O(V)

Answer

O(E)

Answer

O(V × E)