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
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)
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
Explanation: Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.
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
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
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) Using level ordered search
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
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
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
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.
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.
- Get Free Certificate of Merit in Data Structure II
- Participate in Data Structure II Certification Contest
- Become a Top Ranker in Data Structure II
- Take Data Structure II Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10