Representation of Graphs MCQ Quiz in తెలుగు - Objective Question with Answer for Representation of Graphs - ముఫ్త్ [PDF] డౌన్‌లోడ్ కరెన్

Last updated on Mar 16, 2025

పొందండి Representation of Graphs సమాధానాలు మరియు వివరణాత్మక పరిష్కారాలతో బహుళ ఎంపిక ప్రశ్నలు (MCQ క్విజ్). వీటిని ఉచితంగా డౌన్‌లోడ్ చేసుకోండి Representation of Graphs MCQ క్విజ్ Pdf మరియు బ్యాంకింగ్, SSC, రైల్వే, UPSC, స్టేట్ PSC వంటి మీ రాబోయే పరీక్షల కోసం సిద్ధం చేయండి.

Latest Representation of Graphs MCQ Objective Questions

Top Representation of Graphs MCQ Objective Questions

Representation of Graphs Question 1:

Which of the following statements is false?

  1. The breadth first search takes O(V+E) time for a graph with a vertex set V and edge set E.
  2. BFS discovers all vertices at distance k from the source before discovering any vertices at distance k+1.
  3. A directed graph G is acyclic (DAG) iff a depth first search of G yields no back edges.
  4. There are (k+1) connected components in a graph G if a depth first traversal is done on G with n vertices and k tree edges.

Answer (Detailed Solution Below)

Option 4 : There are (k+1) connected components in a graph G if a depth first traversal is done on G with n vertices and k tree edges.

Representation of Graphs Question 1 Detailed Solution

Out of all the statements, option 4 is false because there are (n-k) connected components in a graph G if a depth first traversal is done on G with n vertices and k tree edges.

Representation of Graphs Question 2:

The transpose of a directed graph G = (V,E) is the graph GT = (V,E). Thus, GT is G with all its edges reversed. Then running time to compute GT from G for adjacency-matrix representations is ______.

  1. O(|V + E|2)
  2. O(|V + E|)
  3. O(2|V|)
  4. O(|V|2)

Answer (Detailed Solution Below)

Option 4 : O(|V|2)

Representation of Graphs Question 2 Detailed Solution

For the adjacency matrix representation, to compute the graph transpose, flip a matrix over its diagonal i.e. swap all the rows of a given matrix into columns and vice-versa.  This takes time O(|V|2).

For the adjacency list representation, it requires a scan through all of the lists, it only takes time O(|E| + |V|).

Representation of Graphs Question 3:

Match the following :

(P) All pairs shortest path

1. Binary trees

(Q) Depth first search

2. queue

(R) Breadth first search

3. Stack

(S) Huffman coding

4. Matrix

  1. P – 2, Q – 1, R – 3, S – 4
  2. P – 4, Q – 3, R – 1, S – 2
  3. P – 4, Q – 3, R – 2, S – 1
  4. P – 1, Q – 2, R – 3, S – 4

Answer (Detailed Solution Below)

Option 3 : P – 4, Q – 3, R – 2, S – 1

Representation of Graphs Question 3 Detailed Solution

l.h.s techniques are implemented using the r.h.s data structures.

Representation of Graphs Question 4:

The number of strongly connected components in the following graph are :

Gate CS Algorithms Chapter-4 Images-Q4

  1. 3
  2. 7
  3. 5
  4. none of the above

Answer (Detailed Solution Below)

Option 3 : 5

Representation of Graphs Question 4 Detailed Solution

Two nodes u and v of a directed graph are connected if there is a path from u to v and from v to u. This relation partition the vertex set V of the graph into disjoint sets of strongly connected components.

Gate CS Algorithms Chapter-4 Images-Q4.1

Representation of Graphs Question 5:

Match the pairs :

a.Articulation                                         

1.Stack

b. DFS

2. Queue

c. BFS

3. Binary tree

d. Huffman coding

4. Network topology

  1. a-4, b-1, c-3, d-2
  2. a-1, b-1, c-2, d-4
  3. a-4, b-1, c-2, d-3
  4. a-1, b-2, c-3, d-4

Answer (Detailed Solution Below)

Option 3 : a-4, b-1, c-2, d-3

Representation of Graphs Question 5 Detailed Solution

Self-explanation. The right hand side data structures are used to implement the left hand side techniques.
Get Free Access Now
Hot Links: teen patti apk all teen patti game teen patti flush