Help authour, Buy PDF Ebook >>>Click Here<<<
Data Structure Questions and Answers-Topological Sort
Click on any option to know the CORRECT ANSWERS
Question 1 |
Topological sort can be applied to which of the following graphs?
Undirected Cyclic Graphs | |
Directed Cyclic Graphs | |
Undirected Acyclic Graphs | |
Directed Acyclic Graphs |
Question 1 Explanation:
Every Directed Acyclic Graph has one or more topological ordering whereas Cyclic and Undirected graphs can't be ordered topologically.
Question 2 |
Most Efficient Time Complexity of Topological Sorting is? (V - number of vertices, E - number of edges)
O(V + E) | |
O(V) | |
O(E) | |
None of the mentioned |
Question 2 Explanation:
The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).
Question 3 |
Topological sort starts from a node which has?
Maximum Degree | |
Minimum Degree | |
Any degree | |
None of the mentioned |
Question 3 Explanation:
Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.
Question 4 |
What can be the applications of topological sorting?
Finding prerequisite of a task | |
Finding Deadlock in an Operating System | |
Finding Cycle in a graph | |
All of the mentioned |
Question 4 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.
Question 5 |
Topological sort of a Directed Acyclic graph is?
Always unique | |
Always Not unique | |
Sometimes unique and sometimes not unique | |
None of the mentioned |
Question 5 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.
There are 5 questions to complete.