ALGORITHMS |Gate-2004| Previous Year Questions| Set-12

previous year question of ALGORITHMS gate 1993

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 searchI.T(n) = T(n-k) + T(k) + cn
Q.Merge sortII.T(n) = 2T(n-1) + 1
R.Quick sortIII.T(n) = 2T(n/2) + cn
S.Tower of HanoiIV.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|


Back to GATE-HOME


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *