Q1. Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees..
A. 15.
B. 8.
C. 16.
D. 13.
Answer= 16
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.
Answer= A minimum spanning tree
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.
Answer= find minimum spanning tree
Q6. Kruskal’s algorithm is a ______.
A. divide and conquer algorithm.
B. dynamic programming algorithm.
C. greedy algorithm.
D. approximation algorithm.
Answer= greedy 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).
Answer= O(E log V)
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.
Answer= FALSE
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).
Answer= O(V2)
Q14. Prim’s algorithm is a ______.
A. Divide and conquer algorithm.
B. Greedy algorithm.
C. Dynamic Programming.
D. Approximation algorithm.
Answer= Greedy 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.
Answer= 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.
Answer= d-ary heap
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.
Answer= Single source shortest path
Q19. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?.
A. Max priority queue.
B. Stack.
C. Circular queue.
D. Min priority queue.
Answer= Min priority queue