| A. | 6 |
| B. | 42 |
| C. | 132 |
| D. | 256 |
|
Option: C Explanation : Click on Discuss to view users comments. |
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. | θ(n lg n) |
| D. | θ(n2) |
|
Option: D Explanation : Click on Discuss to view users comments. |
| 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] |
|
Option: C Explanation : Click on Discuss to view users comments. |
Match the following :
(a) Huffman codes (i) O(n2)
(b) Optimal polygon triangulation (ii) θ(n3)
(c) Activity selection problem (iii) O(nlgn)
(d) Quicksort (iv) θ(n)
| A. | (i) (ii) (iv) (iii) |
| B. | (i) (iv) (ii) (iii) |
| C. | (iii) (ii) (iv) (i) |
| D. | (iii) (iv) (ii) (i) |
|
Option: C Explanation : Click on Discuss to view users comments. |
Suppose that we have numbers between 1 and 1,000 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 |
|
Option: C Explanation : Click on Discuss to view users comments. |
