What is the primary purpose of a Minimum Spanning Tree (MST)?
A) To find the longest path in a graph
B) To connect all vertices with the minimum total edge weight
C) To find the shortest path between two vertices
D) To detect cycles in a graph
Answer: B) To connect all vertices with the minimum total edge weight
Which algorithm is based on the greedy method and uses edge weights?
A) Dijkstra’s algorithm
B) Bellman-Ford algorithm
C) Kruskal’s algorithm
D) Floyd-Warshall algorithm
Answer: C) Kruskal’s algorithm
What is the key data structure used in Kruskal’s algorithm to manage sets of vertices?
A) Array
B) Stack
C) Priority queue
D) Disjoint-set (Union-Find)
Answer: D) Disjoint-set (Union-Find)
In Prim’s algorithm, which data structure is typically used to select the next vertex?
A) Stack
B) Queue
C) Priority queue
D) Array
Answer: C) Priority queue
What is the time complexity of Kruskal’s algorithm using a union-find structure?
A) O(E log E)
B) O(V + E)
C) O(E + V log V)
D) O(V^2)
Answer: A) O(E log E)
What is the time complexity of Prim’s algorithm using a binary heap?
A) O(E)
B) O(E + V log V)
C) O(V^2)
D) O(V log V)
Answer: B) O(E + V log V)
What is a key characteristic of Kruskal’s algorithm?
A) It always starts from a specific vertex
B) It grows the MST by adding edges one by one
C) It considers all vertices at the same time
D) It cannot handle disconnected graphs
Answer: B) It grows the MST by adding edges one by one
In Prim’s algorithm, how is the next vertex chosen to add to the MST?
A) The vertex with the least number of edges
B) The vertex with the minimum edge weight connected to the MST
C) The vertex with the maximum edge weight
D) The vertex farthest from the current tree
Answer: B) The vertex with the minimum edge weight connected to the MST
Which algorithm is better for dense graphs?
A) Kruskal’s algorithm
B) Prim’s algorithm
C) Both are equally efficient
D) Neither is efficient for dense graphs
Answer: B) Prim’s algorithm
What happens if there is a cycle formed while adding edges in Kruskal’s algorithm?
A) The cycle is accepted
B) The edge causing the cycle is discarded
C) The algorithm restarts
D) The edge is added anyway
Answer: B) The edge causing the cycle is discarded
Which of the following is true about the Minimum Spanning Tree?
A) It can have cycles
B) It includes all vertices
C) It can be disconnected
D) It must include the heaviest edge
Answer: B) It includes all vertices
What is the role of the union operation in Kruskal’s algorithm?
A) To merge two different trees
B) To find the shortest path
C) To create new edges
D) To delete edges
Answer: A) To merge two different trees
Which algorithm can be more efficient when the graph is represented as an adjacency matrix?
A) Kruskal’s algorithm
B) Prim’s algorithm
C) Both algorithms perform equally
D) Neither algorithm is suitable
Answer: B) Prim’s algorithm
What will happen if Kruskal’s algorithm is applied to a graph with only one vertex?
A) It will return an empty tree
B) It will return the vertex itself
C) It will return an error
D) It will form a cycle
Answer: A) It will return an empty tree
Which of the following statements is true about Prim’s algorithm?
A) It can start from any vertex
B) It requires all edges to be sorted
C) It always produces the same MST
D) It cannot handle weighted graphs
Answer: A) It can start from any vertex
What type of graphs can both Kruskal’s and Prim’s algorithms be applied to?
A) Only directed graphs
B) Only undirected graphs
C) Both directed and undirected graphs
D) Only graphs with no cycles
Answer: B) Only undirected graphs
What is the maximum number of edges in a Minimum Spanning Tree for a graph with V vertices?
A) V
B) V-1
C) V+1
D) 2V
Answer: B) V-1
What does the “cut property” of MST state?
A) Any edge can be included in the MST
B) The minimum edge crossing any cut must be in the MST
C) No edge can be included in the MST
D) The cut must include all edges
Answer: B) The minimum edge crossing any cut must be in the MST
Which of the following is a disadvantage of Prim’s algorithm?
A) It cannot find the MST
B) It is slower for sparse graphs
C) It requires sorting edges
D) It cannot handle negative weights
Answer: B) It is slower for sparse graphs
In Kruskal’s algorithm, how are edges sorted?
A) By their vertices
B) By their weights
C) By their colors
D) By their lengths
Answer: B) By their weights
What is the primary advantage of using a priority queue in Prim’s algorithm?
A) It makes the algorithm simpler
B) It reduces the overall time complexity
C) It handles negative weights
D) It guarantees a minimum spanning tree
Answer: B) It reduces the overall time complexity
What does the term “MST” stand for?
A) Minimum Spanning Tree
B) Maximum Spanning Tree
C) Minimum Shortest Tree
D) Maximum Shortest Tree
Answer: A) Minimum Spanning Tree
Which of the following can affect the performance of Kruskal’s algorithm?
A) The number of vertices
B) The number of edges
C) The weight distribution of edges
D) All of the above
Answer: D) All of the above
What is the relationship between MST and total edge weight?
A) MST has the maximum total edge weight
B) MST has the minimum total edge weight
C) MST’s weight is irrelevant
D) MST cannot be computed without edge weights
Answer: B) MST has the minimum total edge weight
Which algorithm is more suitable for finding an MST in a graph with many edges?
A) Kruskal’s algorithm
B) Prim’s algorithm
C) Both algorithms are equally suitable
D) Neither algorithm is suitable
Answer: B) Prim’s algorithm
How many times can an edge be added in Kruskal’s algorithm?
A) Once
B) Multiple times
C) As many as needed
D) It depends on the graph
Answer: A) Once
What will be the result if the graph is not connected when applying Kruskal’s algorithm?
A) It will return an empty tree
B) It will return a spanning forest
C) It will fail
D) It will include all vertices
Answer: B) It will return a spanning forest
What is the main function of the find operation in the union-find structure?
A) To add edges
B) To find the root of a set
C) To sort edges
D) To merge two sets
Answer: B) To find the root of a set
Which algorithm would you use if you want to ensure that the MST includes the smallest edge at every step?
A) Dijkstra’s algorithm
B) Kruskal’s algorithm
C) Prim’s algorithm
D) Bellman-Ford algorithm
Answer: C) Prim’s algorithm
What is the result of executing Kruskal’s algorithm on a fully connected graph?
A) It will create a cycle
B) It will form a tree
C) It will include all vertices without edges
D) It cannot be executed
Answer: B) It will form a tree
How does Prim’s algorithm initially choose edges?
A) By weight
B) By random selection
C) By input order
D) By vertex degree
Answer: A) By weight
Which of the following statements about the union-find structure is true?
A) It is used to manage a list of vertices
B) It keeps track of the connected components
C) It can only handle undirected graphs
D) It is not necessary for Kruskal’s algorithm
Answer: B) It keeps track of the connected components
What will happen to the minimum spanning tree if an edge with a smaller weight than those already included is found?
A) It is added to the MST
B) The algorithm restarts
C) It is ignored
D) The existing edges are replaced
Answer: A) It is added to the MST
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