A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).2e

32. A complete graph can have ...............
a. n^2 spanning trees
b. n^(n-2) spanning trees
c. n^(n+1) spanning trees
d. n^n spanning trees
View Answer Report Discuss Too Difficult! Search Google
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
View Answer Report Discuss Too Difficult! Search Google
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)
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).n*(n-1)/2

35. Graphs are represented using ............
a. Adjacency tree
b. Adjacency linked list
c. Adjacency graph
d. Adjacency queue
View Answer Report Discuss Too Difficult! Search Google
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
View Answer Report Discuss Too Difficult! Search Google
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
View Answer Report Discuss Too Difficult! Search Google
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
View Answer Report Discuss Too Difficult!
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
View Answer Report Discuss Too Difficult!
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
View Answer Report Discuss Too Difficult!
Answer: (d).Queue

Page 4 of 17