 111. 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
 Answer: (c).multiply all values by 10

 112. 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

 113. What would be the value of the distance matrix, after the execution of the given code? #include #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 a. a b. b c. c d. d

 114. 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

 115. Every Directed Acyclic Graph has at least one sink vertex. a. True b. False c. May be d. Can't say

 116. 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

 117. The topological sorting of any DAG can be done in ________ time. a. cubic b. quadratic c. linear d. logarithmic
 119. What would be the output of the following C++ program if the given input is0 0 0 1 10 0 0 0 10 0 0 1 01 0 1 0 01 1 0 0 0 #include using namespace std; bool visited; int G;   void fun(int i) { cout<>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