Data Structure Questions and Answers-Topological Sort

DOWNLOAD FREE PDF <<CLICK HERE>>

Data Structure Questions and Answers-Topological Sort

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 2 Explanation: 
The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Topological sort starts from a node which has?
A
Maximum Degree
B
Minimum Degree
C
Any degree
D
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
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.

DOWNLOAD FREE PDF <<CLICK HERE>>