Data Structure Questions and Answers – Directed Acyclic Graph

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Directed Acyclic Graph”.

1. Every Directed Acyclic Graph has at least one sink vertex.
a) True
b) False
View Answer

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

2. Which of the following is not a topological sorting of the given graph?
A B C D F E is not 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) A B C D F E
View Answer

Answer: d
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. In A B C D F E, F comes before E in ordering.

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
View Answer

Answer: a
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.
advertisement
advertisement

4. The topological sorting of any DAG can be done in ________ time.
a) cubic
b) quadratic
c) linear
d) logarithmic
View Answer

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

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
View Answer

Answer: b
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.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. What sequence would the BFS traversal of the given graph yield?
A B D C E F would be the BFS traversal of the given graph yield
a) A F D B C E
b) C B A F E D
c) A B D C E F
d) E F D C B A
View Answer

Answer: c
Explanation: In BFS nodes gets explored and then the neighbors of the current node gets explored, before moving on to the next levels.

7. What would be the output of the following C++ program if the given input is

advertisement
0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
 
#include <bits/stdc++.h>
using namespace std;
bool visited[5];
int G[5][5];
 
void fun(int i)
{
	cout<<i<<" ";
	visited[i]=true;
	for(int j=0;j<5;j++)
		if(!visited[j]&&G[i][j]==1)
			fun(j);
}
 
int main()
{   
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>G[i][j];
 
	for(int i=0;i<5;i++)
		visited[i]=0;
 
	fun(0);
		return 0;
}

a) 0 2 3 1 4
b) 0 3 2 4 1
c) 0 2 3 4 1
d) 0 3 2 1 4
View Answer

Answer: b
Explanation: Given Input is the adjacency matrix of a graph G, whereas the function ‘fun’ prints the DFS traversal.
advertisement

8. Which of the given statement is true?
a) All the Cyclic Directed Graphs have topological sortings
b) All the Acyclic Directed Graphs have topological sortings
c) All Directed Graphs have topological sortings
d) All the cyclic directed graphs hace non topological sortings
View Answer

Answer: d
Explanation: Cyclic Directed Graphs cannot be sorted topologically.

9. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?
a) True
b) False
View Answer

Answer: b
Explanation: If such vertices exists it means that the graph contains a cycle which contradicts the first part of the statement.

10. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
a) Depends on a Graph
b) Will always be zero
c) Will always be greater than zero
d) May be zero or greater than zero
View Answer

Answer: b
Explanation: Every Directed Acyclic Graph has a source and a sink vertex.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.