This set of MCQ on minimum spanning trees and algorithms in data structure includes multiple-choice questions on the design of minimum spanning trees, kruskal’s algorithm, prim’s algorithm, dijkstra and bellman-ford algorithms.

1. Which of the following is/are the operations performed by kruskal’s algorithm.

i) sort the edges of G in increasing order by length ii) keep a subgraph S of G initially empty iii) builds a tree one vertex at a time

A) i, and ii only

B) ii and iii only

C) i and iii only

D) All i, ii and iii

2. Rather than build a subgraph one edge at a time …………………………. builds a tree one vertex at a time.

A) kruskal’s algorithm

B) prim’s algorithm

C) dijkstra algorithm

D) bellman ford algorithm

3. ……………… is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to subgraph S.

A) Kruskal’s algorithm

B) Prim’s algorithm

C) Dijkstra algorithm

D) Bellman ford algorithm

4. The result of prim’s algorithm is a total time bound of ………………

A) O(logn)

B) O(m+n logn)

C) O(mn)

D) O(m logn)

5. The ………………… process updates the costs of all the vertices V, connected to a vertex U, if we could improve the best estimate of the shortest path to V by including (U,V) in the path to V.

A) relaxation

B) improvement

C) shortening

D) Costing

6. …………….. turns out that one can find the shortest paths from a given source to all points in a graph in the same time.

A) Kruskal’s algorithm

B) Prim’s algorithm

C) Dijkstra algorithm

D) Bellman ford algorithm

7. ……………. keeps two sets of vertices; S, the set of vertices whose shortest paths from the source have already been determined and V-S, the remaining vertices.

A) Kruskal’s algorithm

B) Prim’s algorithm

C) Dijkstra algorithm

D) Bellman ford algorithm

8. …………….. is a more generalized single source shortest path algorithm which can find t he shortest path in a graph with negative weighted edges.

A) Kruskal’s algorithm

B) Prim’s algorithm

C) Dijkstra algorithm

D) Bellman ford algorithm

9. A sample application of …………….. algorithm is to solve critical path problem, i.e. finding the longest path through a DAG.

A) DAG application path algorithm

B) DAG shortest path algorithm

C) DAG critical path algorithm

D) Bellman ford algorithm

10. The floyd-warshall all pairs shortest path algorithm computes the shortest paths between each pair of nodes in …………………..

A) O(logn)

B) O(n^2)

C) O(mn)

D) O(n^3)

11. In a directed graph, the …………….. can compute the transitive hull in O(n^3)

A) Transitive Hull

B) Minimax Distance

C) Max Min Distance

D) Safest Path

12. ……………… means, for all vertices, compute its reachability.

A) Transitive Hull

B) Minimax Distance

C) Max Min Distance

D) Safest Path

13. For a directed graph with edge lengths, the floyd warshall algorithm can compute the …………….. between each pair of nodes in O(n^3).

A) Transitive Hull

B) Minimax Distance

C) Max Min Distance

D) Safest Path

14. Given a directed graph where the edges are labeled with survival probabilities, we can compute the …………… between the two nodes with floyd warshall.

A) Transitive Hull

B) Minimax Distance

C) Max Min Distance

D) Safest Path

15. ………………… describe efficient algorithms for computing G^T from G, for both the adjacency list and adjacency matrix representations of G.

A) Graph transpose problem

B) Strongly connected components problem

C) Topological sort problem

D) Euler path problem

16. In …………… input is a directed acyclic graph (DAG)G=(V,E).

A) Graph transpose problem

B) Strongly connected components problem

C) Topological sort problem

D) Euler path problem

17. In …………………., a directed graph G is acylic if and only if a DFS of G yields no back edge.

A) Graph transpose problem

B) Strongly connected components problem

C) Topological sort problem

D) Euler path problem

18. …………….. is a most generalized single source shortest path algorithm to find the shortest path in a graph even with negative weights.

A) Kruskal’s algorithm

B) Prim’s algorithm

C) Dijkstra algorithm

D) Bellman ford algorithm

19. ………………… solves the problem of finding the shortest path from a point in a graph to a destination.

A) Kruskal’s algorithm

B) Prim’s algorithm

C) Dijkstra algorithm

D) Bellman ford algorithm

20. Dijkstra algorithm is also called the …………………. shortest path problem.

A) multiple source

B) single source

C) single destination

D) multiple destination

**Answers**

1. A) i, and ii only

2. B) prim’s algorithm

3. A) Kruskal’s algorithm

4. B) O(m+n logn)

5. A) relaxation

6. C) Dijkstra algorithm

7. C) Dijkstra algorithm

8. D) Bellman ford algorithm

9. B) DAG shortest path algorithm

10. D) O(n^3)

11. A) Transitive Hull

12. A) Transitive Hull

13. B) Minimax Distance

14. D) Safest Path

15. A) Graph transpose problem

16. C) Topological sort problem

17. C) Topological sort problem

18. D) Bellman ford algorithm

19. C) Dijkstra algorithm

20. B) single source