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.

21. A connected graph T without any cycles is called ........
a. free graph
b. no cycle graph
c. non cycle graph
d. circular graph
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).free graph

22. In a graph if E=(u,v) means ......
a. u is adjacent to v but v is not adjacent to u
b. e begins at u and ends at v
c. u is processor and v is successor
d. both b and c
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).both b and c

23. Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:
I. Minimum Spanning Tree of G is always unique.
II. Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
a. I only
b. II only
c. both I and II
d. neither I and II
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).I only

24. Let A be an adjacency matrix of a graph G. The ij th entry in the matrix Ak , gives
a. The number of paths of length K from vertex Vi to vertex Vj.
b. Shortest path of K edges from vertex Vi to vertex Vj.
c. Length of a Eulerian path from vertex Vi to vertex Vj.
d. Length of a Hamiltonian cycle from vertex Vi to vertex Vj.
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Shortest path of K edges from vertex Vi to vertex Vj.

25. For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to
a. 2n
b. (2n-1)/2
c. 2e
d. 4n
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).2e

26. An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?
a. O (n)
b. O (e)
c. O (e+n)
d. O (e-n)
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).O (e+n)

27. A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are
a. more than n
b. more than n
c. more than (n+1)/2
d. more than n(n-1)/2
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).more than n(n-1)/2

28. The maximum degree of any vertex in a simple graph with n vertices is
a. n–1
b. n+1
c. 2n–1
d. n
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).n–1

29. The data structure required for Breadth First Traversal on a graph is
a. queue
b. stack
c. array
d. tree
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).queue

30. In Breadth First Search of Graph, which of the following data structure is used?
a. Stack
b. Queue
c. Linked List
d. None of the above
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Queue

Page 3 of 17