Data Structure Questions and Answers – Topological Sort

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Topological Sort”.

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
View Answer

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) O(V*E)
View Answer

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

3. In most of the cases, topological sort starts from a node which has __________
a) Maximum Degree
b) Minimum Degree
c) Any degree
d) Zero Degree
View Answer

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

4. Which of the following is not an application of topological sorting?
a) Finding prerequisite of a task
b) Finding Deadlock in an Operating System
c) Finding Cycle in a graph
d) Ordered Statistics
View Answer

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. Ordered statistics is an application of Heap sort.

5. Topological sort of a Directed Acyclic graph is?
a) Always unique
b) Always Not unique
c) Sometimes unique and sometimes not unique
d) Always unique if graph has even number of vertices
View Answer

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.
Note: Join free Sanfoundry classes at Telegram or Youtube

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) Using level ordered search
View Answer

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
View Answer

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

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
View Answer

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) In the presence of single node with outdegree 0
View Answer

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.
advertisement

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.