YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS
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 F D B C E | |
C B A F D | |
A B D C F | |
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; }
0 2 3 1 4 | |
0 3 2 4 1 | |
0 2 3 4 1 | |
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?
All the Cyclic Directed Graphs have topological sortings | |
All the Acyclic Directed Graphs have topological sortings | |
All Directed Graphs have topological sortings | |
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?
True | |
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?
Depends on a Graph | |
Will always be zero | |
Will always be greater than zero | |
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.