1.  From a complete graph, by removing maximum _______________ edges, we can construct a spanning tree. 
a.  en+1 
b.  ne+1 
c.  n+e1 
d.  en1 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).en+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.  FloydWarshall's All pair shortest path Algorithm 
d.  Dijkstra's Minimal Spanning Tree Algorithm 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).FloydWarshall'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.  n1 
d.  2n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).n

5.  What will be the runningtime 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.  Ο(V2) 
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
