Question 11 : The travelling salesman problem can be solved using _________
1. A spanning tree
2. A minimum spanning tree
3. Bellman – Ford algorithm
4. DFS traversal
View Answer   Discuss with Members

Question 12 : Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.
1. 15
2. 8
3. 16
4. 13
View Answer   Discuss with Members

Question 13 : Every graph has only one minimum spanning tree.
1. True
2. False
3.
4.
View Answer   Discuss with Members

Question 14 : Which of the following is false in the case of a spanning tree of a graph G?
1. It is tree that spans G
2. It is a subgraph of the G
3. It includes every vertex of the G
4. It can be either cyclic or acyclic
View Answer   Discuss with Members

Question 15 : Mo's algorithm can only be used for problems where the query can be calculated from the result of the previous query.
1. true
2. false
3.
4.
View Answer   Discuss with Members

Question 16 : What can be the applications of topological sorting?
1. Finding prerequisite of a task
2. Finding Deadlock in an Operating System
3. Finding Cycle in a graph
4. All of the mentioned
View Answer   Discuss with Members

Question 17 : By what factor time complexity is reduced when we apply square root decomposition to a code?
1. n
2. √n
3. n²
4. n^-1/2
View Answer   Discuss with Members

Question 18 : Quickselect's algorithm is similar to which of the following algorithm?
1. Merge sort
2. Quicksort
3. Selection sort
4. Counting sort
View Answer   Discuss with Members

Question 19 : What is the auxiliary space requirement of the quickselect algorithm?
1. O(n²)
2. O(n)
3. O(n log n)
4. O(1)
View Answer   Discuss with Members

Question 20 : When the topological sort of a graph is unique?
1. When there exists a hamiltonian path in the graph
2. In the presence of multiple nodes with indegree 0
3. In the presence of single node with indegree 0
4. None of the mentioned
View Answer   Discuss with Members