Multiple Choice Questions on Topological Sort (Data Structures )

1. Topological sort can be applied to which of the following graphs?

a) Undirected Cyclic Graphs
b) Directed Cyclic Graphs
c) Undirected Acyclic Graphs
d) Directed Acyclic Graphs

Answer: d

Explanation: Every Directed Acyclic Graph has one or more topological ordering whereas Cyclic and Undirected graphs can’t be ordered topologically.

2. Most Efficient Time Complexity of Topological Sorting is? (V – number of vertices, E – number of edges)

a) O(V + E)
b) O(V)
c) O(E)
d) None of the mentioned

Answer: a

Explanation: The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).

3. Topological sort starts from a node which has?

a) Maximum Degree
b) Minimum Degree
c) Any degree
d) None of the mentioned

Answer: b

Explanation: Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.

4. What can be the applications of topological sorting?

a) Finding prerequisite of a task
b) Finding Deadlock in an Operating System
c) Finding Cycle in a graph
d) All of the mentioned

Answer: d

Explanation: Topological sort tells what task should be done before a task can be started. It also detects cycle in the graph which is why it is used in the Operating System to find the deadlock.

5. Topological sort of a Directed Acyclic graph is?

a) Always unique
b) Always Not unique
c) Sometimes unique and sometimes not unique
d) None of the mentioned

Answer: c

Explanation: The topological sort of a graph can be unique if we assume the graph as a single linked list and we can have multiple topological sort order if we consider a graph as a complete binary tree.

6. Topological sort can be implemented by?

a) Using Depth First Search
b) Using Breadth First Search
c) Using Depth and Breadth First Search
d) None of the mentioned

Answer: c

Explanation: We can implement topological sort by both BFS and DFS. In BFS, we use queue as data structure and in DFS, we use Linked list (if recursive) or Stack (if not recursive) as data structure.

7. Topological sort is equivalent to which of the traversals in trees?

a) Pre-order traversal
b) Post-order traversal
c) In-order traversal
d) Level-order traversal

Answer: a

Explanation: In pre-order traversal of trees, we process the root first and then child from left to right.

8. A man wants to go different places in the world. He has listed them down all. But there are some places where he wants to visit before some other places. What application of graph can he use to determine that?

a) Depth First Search
b) Breadth First Search
c) Topological Sorting
d) Dijkstra’s Shortest path algorithm

Answer: c

Explanation: As the definition of topological sorting suggests, it is the way to do tasks in prescribed order. So, if he does topological sorting, it will be easy for him to recognize what should be the order to visit different places.

9. When the topological sort of a graph is unique?

a) When there exists a hamiltonian path in the graph
b) In the presence of multiple nodes with indegree 0
c) In the presence of single node with indegree 0
d) None of the mentioned

Answer: a

Explanation: A hamiltonian path exists in a Directed Acyclic Graph when all pairs of consecutive vertices are in sorted order and are connected by edges. In such a case, there exists a unique topological sorting order.