Data Structures Multiple Choice Questions and Answers on Directed Graph

1. Dijkstra’s Algorithm will work for both negative and positive weights?

a) True
b) False
Answer: b

Explanation: Dijkstra’s Algorithm assumes all weights to be non-negative.
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
Answer: a

Explanation: This is a part of the nomenclature followed in Graph Theory.
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
Answer: b

Explanation:Direct_Graph
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)
Answer: b

Explanation: The Algorithm uses Dynamic Programming and checks for every possible path.
5. All Graphs have unique representation on paper.

a) True
b) False
Answer: False

Explanation: Same Graph may be drawn in different ways on paper.
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
Answer: c

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.
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
Answer: d

Explanation: If a graph has V vertices than every vertex can be connected to a possible of V-1 vertices.
8. What would be the DFS traversal of the given Graph?

Dire_graph_3.html   draw.io
a) ABCED
b) AEDCB
c) EDCBA
d) ADECB
Answer: a

Explanation: In this case two answers are possible including ADEBC.
9. What would be the value of the distance matrix, after the execution of the given code?

  1. #include 
  2. #define INF 1000000
  3. int graph[V][V] = {   {0,   7,  INF, 4},
  4.                       {INF, 0,   13, INF},
  5.                       {INF, INF, 0,   12},
  6.                       {INF, INF, INF, 0}
  7.                   };
  8.  
  9. int distance[V][V], i, j, k;
  10.  
  11. for (i = 0; i < V; i++)
  12.         for (j = 0; j < V; j++)
  13.     	distance[i][j] = graph[i][j];
  14.  
  15. for (k = 0; k < V; k++)
  16. 	for (i = 0; i < V; i++)
  17.         	for (j = 0; j < V; j++)
  18.                 {
  19.             		if (distance[i][k] + distance[k][j] < distance[i][j])
  20.                 		distance[i][j] = distance[i][k] + distance[k][j];
  21.  
  22.                            return 0;
  23.                 }
a)
  1.                 {            
  2.                         {0,   7,  INF, 4},
  3.                         {INF, 0,   13, INF},
  4.                         {INF, INF, 0,   12},
  5.                         {INF, INF, INF, 0}
  6.                 };
b)
  1.                 {            
  2.                         {0,   7,  20, 24},
  3.                         {INF, 0,   13, 25},
  4.                         {INF, INF, 0,   12},
  5.                         {INF, INF, INF, 0}
  6.                 };
c)
  1.                   { 
  2.                         {0,   INF,  20, 24},
  3.                         {INF, INF,   13, 25},
  4.                         {INF, INF, 0,   12},
  5.                         {INF, INF, INF, 0}
  6.                         {INF, 0,   13, 25},
  7.                         {INF, INF, 0,   12},
  8.                         {24, INF, INF, 0}
  9.                   };
d) None of the mentioned
Answer: b

Explanation: The program computes the shortest sub distances.
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
Answer: c

Explanation: If the no cycles exists then the difference between the number of vertices and edges is 1.

Related

Computer Fundamentals Multiple choice Questions and Answers on Digitizers for Freshers

1. Input Devices that use a special ink that is used for converting pictures, maps and drawings into digital format. a) Digitizersb) Digital pensc) Light Pensd) MICR Answer: a Explanation: The di...

Multiple choice Questions and Answers on Backup Types of Cloud Computing for Freshers

1. Which of the following flag is used by backup software to specify whether a file should be backed up or not ? a) archive bitb) passive bitc) active bitd) all of the mentioned Answer: a Explana...

Computer Fundamentals Multiple choice Questions and Answers on Output Devices for Freshers

1. Input Devices that use a special ink that contains magnetizable particles of iron oxide are ____ a) Optical disksb) Magnetic disksc) MICRd) Magnetic drives Answer: c Explanation: MICR reads da...

Post a Comment

emo-but-icon
:noprob:
:smile:
:shy:
:trope:
:sneered:
:happy:
:escort:
:rapt:
:love:
:heart:
:angry:
:hate:
:sad:
:sigh:
:disappointed:
:cry:
:fear:
:surprise:
:unbelieve:
:shit:
:like:
:dislike:
:clap:
:cuff:
:fist:
:ok:
:file:
:link:
:place:
:contact:

item