Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Directed Acyclic Graph

1 - Question

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

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

2 - Question

Which of the following 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

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 - Question

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

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.

4 - Question

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

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

5 - Question

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

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.

6 - Question

What sequence would 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

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

7 - Question

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;
int G;

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

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

8 - Question

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

Explanation: Cyclic Directed Graphs cannot be sorted topologically.

9 - Question

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

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

10 - Question

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