Data Structure Questions and Answers-Directed Acyclic Graph

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Directed Acyclic Graph

Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What sequence would the BFS traversal of the given graph yield?
A
A F D B C E
B
C B A F D
C
A B D C F
D
F D C B A
Question 6 Explanation: 
In BFS nodes gets explored and then the neighbors of the current node gets explored, before moving on to the next levels.

Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What would be the output of the following C++ program if the given input is

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
Question 7 Explanation: 
Given Input is the adjacency matrix of a graph G, whereas the function 'fun' prints the DFS traversal.

Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
None of the given statements is true
Question 8 Explanation: 
Cyclic Directed Graphs cannot be sorted topologically.

Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 9 Explanation: 
If such vertices exists it means that the graph contains a cycle which contradicts the first part of the statement.

Question 10 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 10 Explanation: 
Every Directed Acyclic Graph has a source and a sink vertex.

There are 10 questions to complete.