adplus-dvertising
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
Answer: (d).56

113. 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
a. a
b. b
c. c
d. d
Answer: (b).b

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
Answer: (c).6

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

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
Answer: (a).(V*(V-1))/2

117. The topological sorting of any DAG can be done in ________ time.
a. cubic
b. quadratic
c. linear
d. logarithmic
Answer: (c).linear

118. 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
Answer: (b).No Hamiltonian path is possible

119. 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[5];
int G[5][5];
 
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
Answer: (b).0 3 2 4 1

120. 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. None of the given statements is true
Answer: (a).All the Cyclic Directed Graphs have topological sortings