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