Data Structures and Algorithms Multiple choice Questions and Answers-Graphs

31.	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

Discuss

Answer: (c).2e

Discuss

Answer: (b). n^(n-2) spanning trees

33.	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

Discuss

Answer: (c).trees have root

34.	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)

Discuss

Answer: (c).n*(n-1)/2

35.	Graphs are represented using ............
a.	Adjacency tree
b.	Adjacency linked list
c.	Adjacency graph
d.	Adjacency queue

Discuss

Answer: (b).Adjacency linked list

36.	The spanning tree of connected graph with 10 vertices contains ..............
a.	9 edges
b.	11 edges
c.	10 edges
d.	9 vertices

Discuss

Answer: (a).9 edges

37.	If locality is a concern, you can use ................ to traverse the graph.
a.	Breadth First Search
b.	Depth First Search
c.	Either BFS or DFS
d.	None of these

Discuss

Answer: (b).Depth First Search

38.	Which of the following algorithms solves the all-pair shortest path problem?
a.	Floyd's algorithm
b.	Prim's algorithm
c.	Dijkstra's algorithm
d.	Warshall's algorithm

Discuss

Answer: (a).Floyd's algorithm

39.	The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is
a.	1
b.	2
c.	3
d.	4

Discuss

Answer: (b).2

40.	Which of the following is useful in traversing a given graph by breadth first search?
a.	set
b.	List
c.	stacks
d.	Queue

Discuss

Answer: (d).Queue