31.
The number of different binary trees with 6
nodes is .............

(A) 6 (B) 42

(C) 132 (D) 256

Answer: C

32. Let
A[1...n] be an array of n distinct numbers. If i<j and A[i]>A[j], then the
pair (i,j) is called an inversion of A. What is the expected number of
inversions in any permutation on n elements?

(A) Î¸(n) (B) Î¸(lg n)

(C) Î¸(nlg n) (D) Î¸(n

^{2})
Answer: D

33. Which
one of the following array represents a binary max-heap?

(A) [26, 13,
17, 14, 11, 9, 15]

(B) [26, 15,
14, 17, 11, 9, 13]

(C) [26, 15,
17, 14, 11, 9, 13]

(D) [26, 15,
13, 14, 11, 9, 17]

Answer: C

34. Match
the following:

(a) Huffman
codes (i) O(n

^{2})
(b) Optimal
polygon triangulation (ii) Î¸(n

^{3})
(c) Activity
selection problem (iii) O(nlgn)

(d)
Quicksort (iv)
Î¸(n)

**Codes:**

(a)
(b) (c) (d)

(A) (i) (ii)
(iv) (iii)

(B) (i) (iv)
(ii) (iii)

(C)
(iii) (ii) (iv)
(i)

(D)
(iii) (iv) (ii)
(i)

Answer: C

35. Suppose
that we have numbers between 1 and 1000 in a binary search tree and want to
search for the number 364. Which of the following sequences could not be the
sequence of nodes examined?

(A) 925,
221, 912, 245, 899, 259, 363, 364

(B) 3, 400,
388, 220, 267, 383, 382, 279, 364

(C) 926,
203, 912, 241, 913, 246, 364

(D) 3, 253,
402, 399, 331, 345, 398, 364

Answer: C

36. A
triangulation of a polygon is a set of T chords that divide the polygon into
disjoint triangles. Every triangulation of n-vertex convex polygon has
................ chords and divides the polygon into ............... triangles.

(A) n-2, n-1 (B) n-3, n-2

(C) n-1, n (D) n-2, n-2

Answer: B

37. Implicit
return type of a class constructor is:

(A) not of
class type itself (B) class type
itself

(B) a
destructor of class type (D) a destructor
not of class type

Answer: B

38. It
is possible to define a class within a class termed as nested class. There are
............ types of nested classes.

(A) 2 (B) 3

(C) 4 (D) 5

Answer: A, C

39. Which
of the following statements is correct?

(A) Aggregation
is a strong type of association between two classes with full ownership.

(B) Aggregation
is a strong type of association between two classes with partial ownership.

(C)
Aggregation is a weak type of association between two classes with partial
ownership.

(D)
Aggregation is a weak type of association between two classes with full
ownership.

Answer: C

40. Which
of the following statements is correct?

(A) Every
class containing abstract method must not be declared abstract.

(B) Abstract
class cannot be directly initiated with ‘new’ operator.

(C) Abstract
class cannot be initiated.

(D) Abstract
class contains definition of implementation.

Answer: B,C

## 0 Comments