# Minimum Spanning Tree MCQs

Q1. Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees..

A. 15.

B. 8.

C. 16.

D. 13.

Q2. The travelling salesman problem can be solved using _________.

A.  A spanning tree.

B.  A minimum spanning tree.

C.  Bellman – Ford algorithm.

D.  DFS traversal.

Q3. Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?.

A.  Every minimum spanning tree of G must contain CD.

B.  If AB is in a minimum spanning tree, then its removal must disconnect G.

C.  No minimum spanning tree contains AB.

D.  G has a unique minimum spanning tree.

Answer=  No minimum spanning tree contains AB

Q4. Which of the following is false?.

A.  The spanning trees do not have any cycles.

B.  MST have n – 1 edges if the graph has n edges.

C.  Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph.

D.  Removing one edge from the spanning tree will not make the graph disconnected.

Answer=  Removing one edge from the spanning tree will not make the graph disconnected

Q5. Kruskal’s algorithm is used to ______.

A.  find minimum spanning tree.

B.  find single source shortest path.

C.  find all pair shortest path algorithm.

D.  traverse the graph.

Q6. Kruskal’s algorithm is a ______.

A.  divide and conquer algorithm.

B.  dynamic programming algorithm.

C.  greedy algorithm.

D.  approximation algorithm.

Q7. What is the time complexity of Kruskal’s algorithm?.

A.  O(log V).

B.  O(E log V).

C.  O(E2).

D.  O(V log E).

Q8. Which of the following is true?.

A.  Prim’s algorithm can also be used for disconnected graphs.

B.  Kruskal’s algorithm can also run on the disconnected graphs.

C.  Prim’s algorithm is simpler than Kruskal’s algorithm.

D.  In Kruskal’s sort edges are added to MST in decreasing order of their weights.

Answer=  Kruskal’s algorithm can also run on the disconnected graphs

Q9. Which of the following is false about the Kruskal’s algorithm?.

A.  It is a greedy algorithm.

B.  It constructs MST by selecting edges in increasing order of their weights.

C.  It can accept cycles in the MST.

D.  It uses union-find data structure.

Answer=  It can accept cycles in the MST

Q10. Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q11. Consider the following statements.S1. Kruskal’s algorithm might produce a non-minimal spanning tree.S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure..

A.  S1 is true but S2 is false.

B.  Both S1 and S2 are false.

C.  Both S1 and S2 are true.

D.  S2 is true but S1 is false.

Answer=  S2 is true but S1 is false

Q12. Which of the following is true?.

A.  Prim’s algorithm initialises with a vertex.

B.  Prim’s algorithm initialises with a edge.

C.  Prim’s algorithm initialises with a vertex which has smallest edge.

D.  Prim’s algorithm initialises with a forest.

Answer=  Prim’s algorithm initialises with a vertex

Q13. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?.

A.  O(log V).

B.  O(V2).

C.  O(E2).

D.  O(V log E).

Q14. Prim’s algorithm is a ______.

A.  Divide and conquer algorithm.

B.  Greedy algorithm.

C.  Dynamic Programming.

D.  Approximation algorithm.

Q15. Prim’s algorithm is also known as __________.

A.  Dijkstra–Scholten algorithm.

B.  Bor?vka’s algorithm.

C.  Floyd–Warshall algorithm.

D.  DJP Algorithm.

Q16. Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density..

A.  d-ary heap.

B.  linear search.

C.  fibonacci heap.

D.  binary search.

Q17. Which of the following is false about Prim’s algorithm?.

A.  It is a greedy algorithm.

B.  It constructs MST by selecting edges in increasing order of their weights.

C.  It never accepts cycles in the MST.

D.  It can be implemented using the Fibonacci heap.

Answer=  It constructs MST by selecting edges in increasing order of their weights

Q18. Dijkstra’s Algorithm is used to solve _____________ problems..

A.  All pair shortest path.

B.  Single source shortest path.

C.  Network flow.

D.  Sorting.