SW17: Graph Representations

Question 1

True or False: Adjacency lists are implemented using an array of pointers to linked lists.

Answer 1

TRUE

Question 2

What is the time complexity to check if an edge (u, v) exists in an Adjacency Matrix?
A. O(n)
B. O(log n)
C. O(1)
D. O(n²)

Answer 2

C. O(1)

Question 3

True or False: An adjacency matrix for an undirected graph is always symmetric along the main diagonal.

Answer 3

TRUE

Question 4

In an Adjacency List, the space complexity is proportional to:
A. n²
B. n + m
C. m²
D. n − m

Answer 4

B. n + m

Question 5

Given the following Adjacency Matrix for a directed graph (A: 010, B: 001, C: 100), what is the out-degree of vertex B (Row 2)?
A. 0
B. 3
C. 1
D. 2

Answer 5

C. 1

Question 6

A graph with very few edges relative to the number of vertices is called:
A. Sparse
B. Regular
C. Complete
D. Dense

Answer 6

A. Sparse

Question 7

Given the following Adjacency Matrix for a directed graph (A: 010, B: 001, C: 100), what is the in-degree of vertex A?
A. 2
B. 1
C. 0
D. 3

Answer 7

B. 1

Question 8

True or False: Removing an edge in an Adjacency List takes O(1) time in the worst case.

Answer 8

FALSE

Question 9

For a sparse graph, which representation is generally more space-efficient?
A. Incidence Matrix
B. Adjacency Matrix
C. Adjacency List
D. Edge Matrix

Answer 9

C. Adjacency List

Question 10

A graph where the number of edges is close to n² is called:
A. Acyclic
B. Sparse
C. Dense
D. Bipartite

Answer 10

C. Dense

Question 11

Fill in the Blanks: In an adjacency matrix M, the entry M{ij} is set to 1 (or true) specifically if vertex i is _____ to vertex j.

Answer 11

adjacent

Question 12

In an Adjacency Matrix representation of a graph with n vertices, the space complexity is:
A. O(n²)
B. O(log n)
C. O(n)
D. O(n + m)

Answer 12

A. O(n²)

Question 13

The diagonal entries of an adjacency matrix for a simple graph (no self-loops) are all:
A. 0
B. 1
C. n
D. Undefined

Answer 13

A. 0

Question 14

Fill in the Blanks: Check if edge (u, v) exists (Matrix) to _____.

Answer 14

O(1)

Question 15

Fill in the Blanks: Iterate all neighbors of u (List) to _____.

Answer 15

O(degree(u))

Question 16

Fill in the Blanks: Space Complexity (Matrix) to _____.

Answer 16

O(n^2)

Question 17

Fill in the Blanks: Space Complexity (List) to _____.

Answer 17

O(n+m)

Question 18

Fill in the Blanks: Iterate all neighbors of u (Matrix) to _____.

Answer 18

O(n)

Question 19

In an adjacency matrix M for an unweighted undirected graph, if M₍ᵢⱼ₎ = 1, then:
A. There is no edge between i and j
B. There is an edge between i and j
C. i has degree zero
D. j has degree zero

Answer 19

B. There is an edge between i and j

Question 20

Fill in the Blanks: Unlike unweighted graphs which use binary values, an adjacency matrix for a weighted graph stores the specific _____ (such as cost, distance, or capacity) in the corresponding matrix cell.

Answer 20

weight