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
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
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
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
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
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
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))
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
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
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
Answer: (a).True, True

Page 1 of 17
prepbytes affliate link