Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs

33
Score: 0
Attempted: 0/33

1. 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

2. 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

3. 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)

4. In Prim’s algorithm, which data structure is typically used to select the next vertex?
(A) Stack
(B) Queue
(C) Priority queue
(D) Array

5. 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²)

6. 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²)
(D) O(V log V)

7. 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

8. 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

9. 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

10. 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

11. 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

12. 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

13. 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

14. 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

15. 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

16. 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

17. 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

18. 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

19. 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

20. In Kruskal’s algorithm, how are edges sorted?
(A) By their vertices
(B) By their weights
(C) By their colors
(D) By their lengths

21. 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

22. What does the term “MST” stand for?
(A) Minimum Spanning Tree
(B) Maximum Spanning Tree
(C) Minimum Shortest Tree
(D) Maximum Shortest Tree

23. 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

24. 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

25. 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

26. 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

27. 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

28. 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

29. 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

30. 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

31. How does Prim’s algorithm initially choose edges?
(A) By weight
(B) By random selection
(C) By input order
(D) By vertex degree

32. 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

33. 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

Data Structures MCQs

Basic Concepts

Linear Data Structures MCQs

Non-Linear Data Structures MCQs

Hashing MCQs MCQs

Hash Tables

Sorting and Searching Algorithms MCQs

Miscellaneous

Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs
By: Prof. Dr. Fazal Rehman | Last updated: May 15, 2025

Related Posts: