Chapter:

# 20+ Non Linear Data Structures - Graphs Solved MCQs

Chapters

97
28.5k
Chapter: Non Linear Data Structures - Graphs
1.

## Which of the following statements for a simple graph is correct?

A. Every path is a trail
B. Every trail is a path
C. Every trail is a path as well as every path is a trail
D. Path and trail have no relation
Answer» A. Every path is a trail
2.

## For the given graph(G), which of the following statements is true?

A. G is a complete graph
B. G is not a connected graph
C. The vertex connectivity of the graph is 2
D. none
Answer» C. The vertex connectivity of the graph is 2
3.

## What is the number of edges present in a complete graph having n vertices?

A. (n*(n+1))/2
B. (n*(n-1))/2
C. n
D. Information given is insufficient
4.

A. True
B. False
C. none
D. none
5.

A. 15
B. 3
C. 1
D. 11
6.

A. (n*n-n-2*m)/2
B. (n*n+n+2*m)/2
C. (n*n-n-2*m)/2
D. (n*n-n+2*m)/2
7.

## Which of the following properties does a simple graph not hold?

A. Must be connected
B. Must be unweighted
C. Must have no loops or multiple edges
D. Must have no multiple edges
8.

A. 24
B. 21
C. 25
D. 16
9.

## Which of the following is true?

A. A graph may contain no edges and many vertices
B. A graph may contain many edges and no vertices
C. A graph may contain no edges and no vertices
D. A graph may contain no vertices and many edges
Answer» B. A graph may contain many edges and no vertices
10.

A. v=e
B. v = e+1
C. v + 1 = e
D. v = e-1
11.

A. 1,2,3
B. 2,3,4
C. 2,4,5
D. 1,3,5
12.

## A graph with all vertices having equal degree is known as a

A. Multi Graph
B. Regular Graph
C. Simple Graph
D. Complete Graph
13.

## Which of the following ways can be used to represent a graph?

B. Incidence Matrix
D. No way to represent
14.

## The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is

A. 2((n*(n-1))/2)
B. 2((n*(n+1))/2)
C. 2((n-1)*(n-1))/2)
D. 2((n*n)/2)
15.

A. 1
B. 2
C. 3
D. 4
16.

## Number of vertices with odd degrees in a graph having a eulerian walk is

A. 0
B. Can’t be predicted
C. 2
D. either 0 or 2
Answer» D. either 0 or 2
17.

## How many of the following statements are correct?

A. All cyclic graphs are complete graphs.
B. All complete graphs are cyclic graphs.
C. All paths are bipartite.
D. All cyclic graphs are bipartite.
Answer» B. All complete graphs are cyclic graphs.
18.

A. n-2
B. n
C. 2
D. 0
19.

A. O(E*E)
B. O(V*V)
C. O(E)
D. O(V)
20.

A. (V*(V-1))/2
B. (V*(V+1))/2
C. (V+1)C2
D. (V-1)C2
21.

A. cubic
C. linear
D. logarithmic
22.

## 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
23.

## 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. All the cyclic directed graphs have non topological sortings
Answer» D. All the cyclic directed graphs have non topological sortings
24.

## What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?

A. Depends on a Graph
B. Will always be zero
C. Will always be greater than zero
D. May be zero or greater than zero
Answer» B. Will always be zero