Graphs Questions

MCQ bookmark_border

31.

An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?

A

O (n)

B

O (e)

C

O (e+n)

D

O (e-n)

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

32.

A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are

A

more than n

B

more than n

C

more than (n+1)/2

D

more than n(n-1)/2

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

33.

The maximum degree of any vertex in a simple graph with n vertices is

A

n

B

n+1

C

2n

D

n

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

34.

The data structure required for Breadth First Traversal on a graph is

A

queue

B

stack

C

array

D

tree

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

35.

In Breadth First Search of Graph, which of the following data structure is used?

A

Stack

B

Queue

C

Linked List

D

None of the above

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

36.

For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is

A

ne

B

2n

C

2e

D

e^n

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

37.

A complete graph can have ...............

A

n^2 spanning trees

B

n^(n-2) spanning trees

C

n^(n+1) spanning trees

D

n^n spanning trees

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

38.

Graph traversal is different from a tree traversal, because:

A

trees are not connected

B

graphs may have loops

C

trees have root

D

None of these

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

39.

The number of edges in a simple, n-vertex, complete graph is

A

n*(n-2)

B

n*(n-1)

C

n*(n-1)/2

D

n*(n-1)*(n-2)

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

40.

Graphs are represented using ............

A

Adjacency tree

B

Adjacency linked list

C

Adjacency graph

D

Adjacency queue

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion