**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?

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 [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)

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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.