Data Structure Questions and Answers-Directed Acyclic Graph

 

 Buy/Download all MCQ Ebook   >>>Click Here<<<

Data Structure Questions and Answers-Directed Acyclic Graph

Click on any option to know the CORRECT ANSWERS

Question 1
Every Directed Acyclic Graph has at least one sink vertex.
A
True
B
False
Bank exam Questions answers

Question 1 Explanation: 
A sink vertex is a vertex which has an outgoing degree of zero.

Question 2
Which of the following is a topological sorting of the given graph?
A
A B C D E F
B
A B F E D C
C
A B E C F D
D
All of the Mentioned
English literature Questions answers

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
With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
A
(V*(V-1))/2
B
(V*(V+1))/2
C
(V+1)C2
D
(V-1)C2
Biology Questions answers

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
The topological sorting of any DAG can be done in ..... time.
A
cubic
B
quadratic
C
linear
D
logarithmic
EVS Questions answers

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
If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
A
Many Hamiltonian paths are possible
B
No Hamiltonian path is possible
C
Exactly 1 Hamiltonian path is possible
D
Given information is insufficient to comment anything
ICT Questions answers

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.

 

 Buy/Download all MCQ Ebook >>>CLICK HERE<<<