Data Structure

Directed Graph

Question 1
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.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
)
Explanation:
Question 3
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 4
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 5
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 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 is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
2
4
5
9
Explanation:
Question 8
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 9
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 10
Marks : +2 | -2
Pass Ratio : 100%
What would be the value of the distance matrix, after the execution of the given code?
Explanation: