Data Structure

Directed Graph

Question 1
Marks : +2 | -2
Pass Ratio : 100%
What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
2
4
5
9
Explanation:
Question 2
Marks : +2 | -2
Pass Ratio : 100%
)
Explanation:
Question 3
Marks : +2 | -2
Pass Ratio : 100%
What would be the value of the distance matrix, after the execution of the given code?
Explanation:
Question 4
Marks : +2 | -2
Pass Ratio : 100%
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?
add all values by 10
subtract 10 from all the values
multiply all values by 10
in both the cases of multiplying and adding by 10
Explanation:
In case of addition or subtraction the shortest path may change because the number of edges between different paths may be different, while in case of multiplication path wont change.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?
28
64
256
56
Explanation:
If a graph has V vertices than every vertex can be connected to a possible of V-1 vertices.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
Dijkstra’s Algorithm will work for both negative and positive weights?
True
False
Explanation:
Dijkstra’s Algorithm assumes all weights to be non-negative.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
What would be the DFS traversal of the given Graph?
ABCED
AEDCB
EDCBA
ADECB
Explanation:
In this case two answers are possible including ADEBC.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
A graph having an edge from each vertex to every other vertex is called a ___________
Tightly Connected
Strongly Connected
Weakly Connected
Loosely Connected
Explanation:
This is a part of the nomenclature followed in Graph Theory.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
All Graphs have unique representation on paper.
True
False
Explanation:
Same Graph may be drawn in different ways on paper.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
O(V*V)
O(V*V*V)
O(E*V)
O(E*E)
Explanation:
The Algorithm uses Dynamic Programming and checks for every possible path.