Graphs Questions

MCQ bookmark_border

11.

What will be the running-time of Dijkstra's single source shortest path algorithm, if the graph G(V,E) is stored in form of adjacency list and binary heap is used ?

A

?(|V|2)

B

?(|V| log |V|)

C

?(|E|+|V| log |V|)

D

None of these

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

12.

Maximum degree of any vertex in a simple graph of vertices n is

A

2n - 1

B

n

C

n + 1

D

n - 1

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

13.

If the data collection is in sorted form and equally distributed then the run time complexity of interpolation search is ?

A

?(n)

B

?(1)

C

?(log n)

D

?(log (log n))

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

14.

A directed graph is

A

Weakly connected

B

Strongly Connected

C

Tightly Connected

D

Linearly Connected

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

15.

State True of False.

i) Network is a graph that has weights or costs associated with it.

ii) An undirected graph which contains no cycles is called a forest.

iii) A graph is said to be complete if there is no edge between every pair of vertices.

A

True, False, True

B

True, True, False

C

True, True, True

D

False, True, True

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

16.

State True or False.i) An undirected graph which contains no cycles is called forest.ii) A graph is said to be complete if there is an edge between every pair of vertices.

A

True, True

B

False, True

C

False, False

D

True, False

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

17.

A graph is said to be

A

Partite

B

Bipartite

C

Rooted

D

Bisects

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

18.

A graph is a collection of nodes, called

A

vertices, edges

B

edges, vertices

C

vertices, paths

D

graph node, edges

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

19.

A

A

Network

B

Weighted graph

C

Both A and B

D

None of the above

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

20.

A

A

Directed tree

B

Undirected tree

C

Dis-joint tree

D

Direction oriented tree

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion