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
Comments are closed.