ALGORITHMS |Gate-2004|
1. An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n – 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n – 1)/2⌋, ⌊(n – 3)/2⌋, ….., 0. The time required to construct a heap in this manner is : [GATE – 2004]
a. O(log n)
b. O(n)
c. O(n log log n)
d. O(n log n)
Answer : b)
2. Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE? [GATE – 2004]
a. f(n) + g(n) = O(h(n)) + h(n))
b. f(n) = O(h(n))
c. fh(n) ≠ O(f(n))
d. f(n)h(n) ≠ O(g(n)h(n))
Answer : d)
3. Consider the undirected graph below:
Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree? [GATE – 2004]
a.(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
b. (A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
c. (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
d. (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
Answer : d)
4. Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. [GATE – 2004]
| RECURSIVE ALGORITHM | RECURRENCE RELATION | ||
| P. | Binary search | I. | T(n) = T(n-k) + T(k) + cn |
| Q. | Merge sort | II. | T(n) = 2T(n-1) + 1 |
| R. | Quick sort | III. | T(n) = 2T(n/2) + cn |
| S. | Tower of Hanoi | IV. | T(n) = T(n/2) + 1 |
a. P-II, Q-III, R-IV, S-I
b. P-IV, Q-III, R-I, S-II
c. P-III, Q-II, R-IV, S-I
d. P-IV, Q-II, R-I, S-III
Answer : b)
ALGORITHMS |Gate-2004|