# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

## Data Structure Questions and Answers-Directed Acyclic Graph

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Every Directed Acyclic Graph has at least one sink vertex.

True | |

False |

Question 1 Explanation:

A sink vertex is a vertex which has an outgoing degree of zero.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Which of the following is a topological sorting of the given graph?

A B C D E F | |

A B F E D C | |

A B E C F D | |

All of the Mentioned |

Question 2 Explanation:

Topological sorting is a linear arrangement of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?

(V*(V-1))/2 | |

(V*(V+1))/2 | |

(V+1)C2 | |

(V-1)C2 |

Question 3 Explanation:

The first edge would have an outgoing degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2.... +1 equals (V*(V-1))/2.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

The topological sorting of any DAG can be done in ..... time.

cubic | |

quadratic | |

linear | |

logarithmic |

Question 4 Explanation:

Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

Many Hamiltonian paths are possible | |

No Hamiltonian path is possible | |

Exactly 1 Hamiltonian path is possible | |

Given information is insufficient to comment anything |

Question 5 Explanation:

For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

There are 5 questions to complete.