Graph representations (adjacency matrix vs list) in Data Structures Theory - Practice Questions

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding adjacency matrix size

If a graph has 7 nodes, how many elements does its adjacency matrix contain?

A 14

B 49

C 21

D 7

💡 Hint

An adjacency matrix is a square matrix with size equal to the number of nodes squared.

An adjacency matrix for a graph with n nodes is an n x n matrix. For 7 nodes, it has 7 rows and 7 columns, so 7 × 7 = 49 elements.

📋 Factual

intermediate

Memory efficiency of adjacency list

Which statement about adjacency lists is true for a graph with many nodes but few edges?

A Adjacency lists use less memory than adjacency matrices.

B Adjacency lists always use more memory than adjacency matrices.

C Adjacency lists and matrices use the same memory regardless of edges.

D Adjacency lists cannot represent graphs with few edges.

💡 Hint

Think about how adjacency lists store only existing edges.

Adjacency lists store only the edges that exist, so for graphs with few edges, they use less memory than adjacency matrices, which store all possible connections.

🔍 Analysis

advanced

Time complexity for checking edge existence

Which graph representation allows checking if an edge exists between two nodes in constant time?

A Edge list

B Adjacency list

C Adjacency matrix

D Incidence matrix

💡 Hint

Consider how data is accessed in each representation.

An adjacency matrix stores edges in a 2D array, so checking if an edge exists between two nodes is a simple lookup, which takes constant time.

❓ Comparison

advanced

Best representation for dense graphs

For a graph where most nodes are connected to many others, which representation is generally more efficient?

A Adjacency matrix

B Adjacency list

C Edge list

D None of the above

💡 Hint

Dense graphs have many edges close to the maximum possible.

Adjacency matrices are efficient for dense graphs because they provide quick access and the memory cost is justified by many edges.

❓ Reasoning

expert

Choosing representation for dynamic edge updates

Which graph representation is generally better for a graph where edges are frequently added and removed?

A Adjacency matrix

B Incidence matrix

C Edge list

D Adjacency list

💡 Hint

Think about how easy it is to add or remove edges in each structure.

Adjacency lists allow easy addition and removal of edges by updating lists, while adjacency matrices require changing matrix entries, which can be less efficient for frequent updates.