What is an adjacency matrix?
A) A 1D array representing graph edges
B) A 2D array representing graph connections
C) A list of edges
D) A tree structure
Answer: B) A 2D array representing graph connections
Which representation is more space-efficient for sparse graphs?
A) Adjacency matrix
B) Adjacency list
C) Both are equally efficient
D) None of the above
Answer: B) Adjacency list
In an adjacency matrix, what does a value of 1 indicate?
A) No edge exists
B) An edge exists
C) The graph is directed
D) The graph is weighted
Answer: B) An edge exists
What is the time complexity of checking for the existence of an edge using an adjacency matrix?
A) O(1)
B) O(n)
C) O(n^2)
D) O(log n)
Answer: A) O(1)
What is the primary disadvantage of using an adjacency matrix for graph representation?
A) It is complex to implement
B) It uses too much memory for sparse graphs
C) It does not support weighted graphs
D) It cannot represent directed graphs
Answer: B) It uses too much memory for sparse graphs
Which of the following is true about adjacency lists?
A) They require more memory than adjacency matrices
B) They can represent both directed and undirected graphs
C) They are slower for edge existence checks
D) They cannot represent weighted graphs
Answer: B) They can represent both directed and undirected graphs
For a complete graph with n vertices, what is the size of the adjacency matrix?
A) n
B) n^2
C) n(n-1)/2
D) 2n
Answer: B) n^2
How can you represent weights in an adjacency matrix?
A) Use negative numbers
B) Replace 1s with the weight values
C) Add an extra row
D) Use a separate array
Answer: B) Replace 1s with the weight values
What is the time complexity of traversing all vertices in an adjacency list?
A) O(1)
B) O(n)
C) O(n + e) where e is the number of edges
D) O(n^2)
Answer: C) O(n + e) where e is the number of edges
Which representation is more suitable for dense graphs?
A) Adjacency list
B) Adjacency matrix
C) Edge list
D) None of the above
Answer: B) Adjacency matrix
What would be the space complexity of an adjacency list representation for a graph with n vertices and e edges?
A) O(n)
B) O(n + e)
C) O(n^2)
D) O(e)
Answer: B) O(n + e)
In a directed graph, what does an entry in the adjacency matrix at row i and column j represent?
A) An edge from j to i
B) An edge from i to j
C) An edge between i and j regardless of direction
D) No connection between i and j
Answer: B) An edge from i to j
Which of the following is NOT a benefit of using an adjacency list?
A) Space efficiency for sparse graphs
B) Easier edge traversal
C) Constant time edge existence checks
D) Flexible representation of weights
Answer: C) Constant time edge existence checks
If a graph has m edges, what is the maximum number of edges in an undirected graph with n vertices?
A) n
B) n(n-1)/2
C) n^2
D) n(n+1)/2
Answer: B) n(n-1)/2
Which of the following scenarios favors using an adjacency matrix over an adjacency list?
A) The graph is sparse
B) Frequent edge additions and deletions
C) Frequent edge existence checks
D) Memory constraints are critical
Answer: C) Frequent edge existence checks
How do you represent an undirected graph in an adjacency matrix?
A) Use only half the matrix
B) The matrix must be symmetric
C) Each edge is represented twice
D) Use negative values for edges
Answer: B) The matrix must be symmetric
Which representation allows for easier iteration over a vertex’s neighbors?
A) Adjacency matrix
B) Adjacency list
C) Edge list
D) None of the above
Answer: B) Adjacency list
What happens to the size of the adjacency matrix if the graph grows?
A) It decreases
B) It remains constant
C) It increases quadratically
D) It increases linearly
Answer: C) It increases quadratically
Which representation is typically used in algorithms like Dijkstra’s for finding the shortest path?
A) Adjacency matrix
B) Adjacency list
C) Edge list
D) None of the above
Answer: B) Adjacency list
For an unweighted directed graph, how is an edge represented in the adjacency list?
A) A list of integers
B) A boolean value
C) A pair of vertices
D) A unique identifier
Answer: A) A list of integers
What is the primary advantage of using an adjacency matrix for representing a weighted graph?
A) Simple implementation
B) Space efficiency
C) Quick access to edge weights
D) Easily modified
Answer: C) Quick access to edge weights
Which graph representation is more suitable for implementing a graph using a sparse edge set?
A) Adjacency matrix
B) Adjacency list
C) Both are equally suitable
D) Edge list
Answer: B) Adjacency list
In an adjacency list representation, what data structure is typically used to store neighbors?
A) Array
B) Linked list
C) Hash map
D) All of the above
Answer: D) All of the above
What is a key characteristic of an edge list representation?
A) It is memory-intensive
B) It is compact and simple
C) It is best for dense graphs
D) It cannot represent weighted graphs
Answer: B) It is compact and simple
How does the adjacency matrix represent self-loops?
A) As 0 in the diagonal
B) As 1 in the diagonal
C) As -1 in the diagonal
D) It cannot represent self-loops
Answer: B) As 1 in the diagonal
Which representation allows for more straightforward graph modifications, like adding or removing edges?
A) Adjacency matrix
B) Adjacency list
C) Edge list
D) None of the above
Answer: B) Adjacency list
In an adjacency matrix, how are parallel edges represented?
A) They cannot be represented
B) As a value greater than 1
C) As a separate row
D) By repeating the row
Answer: B) As a value greater than 1
What is the disadvantage of using an edge list for graph traversal?
A) It is complex to implement
B) It requires more memory
C) It is slow for neighbor lookups
D) It cannot represent directed graphs
Answer: C) It is slow for neighbor lookups
Which representation uses more memory for dense graphs?
A) Adjacency list
B) Adjacency matrix
C) Edge list
D) Both use the same memory
Answer: B) Adjacency matrix
Which method is typically faster for iterating through all edges in a graph?
A) Adjacency matrix
B) Adjacency list
C) Edge list
D) None of the above
Answer: C) Edge list
What is the purpose of using a hash table in an adjacency list?
A) To store edge weights
B) To improve edge existence checks
C) To manage memory efficiently
D) To simplify neighbor storage
Answer: B) To improve edge existence checks
What is a common use case for adjacency lists?
A) Storing highly connected networks
B) Representing large, sparse graphs
C) Graph algorithms that require sorting
D) Displaying graph visualization
Answer: B) Representing large, sparse graphs
What type of graphs can be represented using both adjacency matrices and adjacency lists?
A) Directed graphs only
B) Undirected graphs only
C) Weighted graphs only
D) Both directed and undirected graphs
Answer: D) Both directed and undirected graphs
In an undirected graph, how many entries will be present in the adjacency list for a single edge?
A) 1
B) 2
C) Depends on the vertex degree
D) None
Answer: B) 2
Which graph representation typically provides the best performance for dense graphs?
A) Adjacency list
B) Adjacency matrix
C) Edge list
D) None of the above
Answer: B) Adjacency matrix
How does the adjacency list represent a directed edge?
A) Only one vertex is listed
B) Both vertices are listed
C) It cannot represent directed edges
D) It requires additional information
Answer: A) Only one vertex is listed
Which representation makes it easier to find the in-degree of vertices?
A) Adjacency list
B) Adjacency matrix
C) Edge list
D) All representations are equal
Answer: B) Adjacency matrix
Which representation typically requires more complex algorithms for traversals?
A) Adjacency matrix
B) Adjacency list
C) Edge list
D) All representations
Answer: B) Adjacency list
What is the primary benefit of using an adjacency matrix for algorithms like Floyd-Warshall?
A) Simplicity of implementation
B) Fast edge lookups
C) It uses less memory
D) It can only represent undirected graphs
Answer: B) Fast edge lookups
What happens if the graph representation is not suitable for the graph’s characteristics?
A) No impact
B) It can lead to inefficient algorithms
C) It makes traversal impossible
D) It can only affect memory usage
Answer: B) It can lead to inefficient algorithms
Basic Concepts
Non-Linear Data Structures MCQs
Sorting and Searching Algorithms MCQs
- Data Structures MCQs 1
- Data Structures MCQs 2
- Data Structures MCQs 3
- Data Structures MCQs 4
- Data Structures MCQs 5
- Stacks Solved MCQs
- Queues MCQs
- pointer mcqs
- Array MCQs