Data Structure Questions and Answers – Directed Graph

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

1. Dijkstra’s Algorithm will work for both negative and positive weights?
a) True
b) False
View Answer

2. A graph having an edge from each vertex to every other vertex is called a ___________
a) Tightly Connected
b) Strongly Connected
c) Weakly Connected
d) Loosely Connected
View Answer

3. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
a) 2
b) 4
c) 5
d) 9
View Answer

Answer: b
Explanation:

4. Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
a) O(V*V)
b) O(V*V*V)
c) O(E*V)
d) O(E*E)
View Answer

5. All Graphs have unique representation on paper.
a) True
b) False
View Answer

6. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?
a) add all values by 10
b) subtract 10 from all the values
c) multiply all values by 10
d) in both the cases of multiplying and adding by 10
View Answer

7. What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?
a) 28
b) 64
c) 256
d) 56
View Answer

8. What would be the DFS traversal of the given Graph?

a) ABCED
b) AEDCB
c) EDCBA
d) ADECB
View Answer

9. What would be the value of the distance matrix, after the execution of the given code?

#include <bits/stdc++.h>
#define INF 1000000
int graph[V][V] = {   {0,   7,  INF, 4},
                      {INF, 0,   13, INF},
                      {INF, INF, 0,   12},
                      {INF, INF, INF, 0}
                  };
 
int distance[V][V], i, j, k;
 
for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
    	distance[i][j] = graph[i][j];
 
for (k = 0; k < V; k++)
	for (i = 0; i < V; i++)
        	for (j = 0; j < V; j++)
                {
            		if (distance[i][k] + distance[k][j] < distance[i][j])
                		distance[i][j] = distance[i][k] + distance[k][j];
 
                           return 0;
                }

a)

{            
    {0,   7,  INF, 4},
    {INF, 0,   13, INF},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
};

b)

{            
    {0,   7,  20, 24},
    {INF, 0,   13, 25},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
};

c)

{ 
    {0,   INF,  20, 24},
    {INF, INF,   13, 25},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
    {INF, 0,   13, 25},
    {INF, INF, 0,   12},
    {24, INF, INF, 0}
};

d) None of the mentioned
View Answer

10. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?
a) 21
b) 7
c) 6
d) 49
View Answer

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.