DOWNLOAD FREE PDF <<CLICK HERE>>
Data Structure Questions and Answers-Directed Acyclic Graph
Congratulations - you have completed Data Structure Questions and Answers-Directed Acyclic Graph.
You scored %%SCORE%% out of %%TOTAL%%.
Your performance has been rated as %%RATING%%
Your answers are highlighted below.
Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions 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 MCQ multiple objective type questions 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 MCQ multiple objective type questions 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 MCQ multiple objective type questions 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 MCQ multiple objective type questions 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.
Once you are finished, click the button below. Any items you have not completed will be marked incorrect.
There are 5 questions to complete.