A directory of Objective Type Questions covering all the Computer Science subjects.

1.
From a complete graph, by removing maximum _______________ edges, we can construct a spanning tree.
a. e-n+1
b. n-e+1
c. n+e-1
d. e-n-1
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).e-n+1

2.
Minimum number of spanning tree in a connected graph is
a. n
b. n(n - 1)
c. 1
d. 0
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).1

3.
Find the odd out
a. Prim's Minimal Spanning Tree Algorithm
b. Kruskal's Minimal Spanning Tree Algorithm
c. Floyd-Warshall's All pair shortest path Algorithm
d. Dijkstra's Minimal Spanning Tree Algorithm
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Floyd-Warshall's All pair shortest path Algorithm

4.
The minimum number of edges required to create a cyclid graph of n vertices is
a. n
b. n+1
c. n-1
d. 2n
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).n

5.
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
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Ο(|E|+|V| log |V|)

6.
Maximum degree of any vertex in a simple graph of vertices n is
a. 2n - 1
b. n
c. n + 1
d. n - 1
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).n - 1

7.
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))
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).Ο(log (log n))

8.
A directed graph is ………………. if there is a path from each vertex to every other vertex in the digraph.
a. Weakly connected
b. Strongly Connected
c. Tightly Connected
d. Linearly Connected
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Strongly Connected

9.
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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).True, True, False

10.
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
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).True, True

Page 1 of 4

copyright 2016 computer science bitsCompscibits.com