21. Merge sort makes two recursive calls. Which statement is true after these two recursive calls finish, but before the merge step ? [Paper II June2014]
(A) The array elements form a heap.
(A) The array elements form a heap.
(B) Elements in each half of the array are sorted amongst themselves.
(C) Elements in the first half of the array are less than or equal to elements in second half of the array.
(D) All of the above
22. Searching for an element in the hash table requires O(1) time for the ___ time, whereas for direct addressing it holds for the ___ time. [Paper II June 2014]
(A) worst case, average (B) worst case, worst case
(C) average, worst case (D) best, average
23. An algorithm is made up of 2 modules M1 and M2. If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is [Paper II June 2014]
(A) min (h(n), g(n)) (B) max (h(n), g(n))
(C) h(n) + g(n) (D) h(n) * g(n)
24. What is the maximum number of parenthesis that will appear on the stack at any one time for parenthesis expression given by (( ) ( ( ) ) ( ( ) ) ) [Paper II June 2014]
(A) 2 (B) 3
(C) 4 (D) 5
25. The reverse polish notation equivalent to the infix expression ((A + B) * C + D)/(E + F + G) [Paper III June 201 4]
(A) A B + C * D + EF + G + /
(D) All of the above
22. Searching for an element in the hash table requires O(1) time for the ___ time, whereas for direct addressing it holds for the ___ time. [Paper II June 2014]
(A) worst case, average (B) worst case, worst case
(C) average, worst case (D) best, average
23. An algorithm is made up of 2 modules M1 and M2. If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is [Paper II June 2014]
(A) min (h(n), g(n)) (B) max (h(n), g(n))
(C) h(n) + g(n) (D) h(n) * g(n)
24. What is the maximum number of parenthesis that will appear on the stack at any one time for parenthesis expression given by (( ) ( ( ) ) ( ( ) ) ) [Paper II June 2014]
(A) 2 (B) 3
(C) 4 (D) 5
25. The reverse polish notation equivalent to the infix expression ((A + B) * C + D)/(E + F + G) [Paper III June 201 4]
(A) A B + C * D + EF + G + /
(B) A B + C D * + E F + G + /
(C) A B + C * D + E F G + +/
(C) A B + C * D + E F G + +/
(D) A B + C * D + E + F G + /
26. ___ comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. [Paper III December 2013 ]
(A) 2n – 2 (B) n + floor (lg n) – 2
(C) floor (3n/2) – 2 (D) 2 * lg n – 2
27. Let A and B be two n × n matrices. The efficient algorithm to multiply the two matrices has the time complexity [Paper III December 2013 ]
(A) O(n3) (B) O(n2.81)
(C) O(n2.67) (D) O(n2)
28. Assuming there are n keys and each key is in the range [0, m – 1]. The run time of bucket sort is [Paper III December 2013 ]
26. ___ comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. [Paper III December 2013 ]
(A) 2n – 2 (B) n + floor (lg n) – 2
(C) floor (3n/2) – 2 (D) 2 * lg n – 2
27. Let A and B be two n × n matrices. The efficient algorithm to multiply the two matrices has the time complexity [Paper III December 2013 ]
(A) O(n3) (B) O(n2.81)
(C) O(n2.67) (D) O(n2)
28. Assuming there are n keys and each key is in the range [0, m – 1]. The run time of bucket sort is [Paper III December 2013 ]
(A) O(n) (B) O(n * lg n)
(C) O(n * lg m) (D) O(n + m)
29.What is the value of the postfix expression ?
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5) [Paper II December2013]
(A) – 3/8 (B) 8/3
(C) 24 (D) 24
30. If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a nonempty queue ? [Paper II December 2013]
(A) Neither of the pointers change
(B) Only front pointer changes
(C) Only rear pointer changes
(D) Both of the pointers changes
21. B
22. C
23. B
24. B
25. A
26. C
27. B
28. D
29. D
30. C
(C) O(n * lg m) (D) O(n + m)
29.What is the value of the postfix expression ?
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5) [Paper II December2013]
(A) – 3/8 (B) 8/3
(C) 24 (D) 24
30. If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a nonempty queue ? [Paper II December 2013]
(A) Neither of the pointers change
(B) Only front pointer changes
(C) Only rear pointer changes
(D) Both of the pointers changes
SOLUTIONS
22. C
23. B
24. B
25. A
26. C
27. B
28. D
29. D
30. C
