1
GATE CSE 1999
+2
-0.6
If T1 = O(1), give the correct matching for the following pairs:

List - I

(M) Tn = Tn - 1 + n
(N) Tn = Tn/2 + n
(O) Tn = Tn/2 + nlog n
(P) Tn = Tn - 1 + log n

List - II

(U) Tn= O(n)
(V) Tn = O(nlogn)
(W) Tn = O(n2)
(X) Tn = O(log2n)
A
M – W N – V O – U P – X
B
M – W N – U O – X P – V
C
M – V N – W O – X P – U
D
M – W N – U O – V P – X
2
GATE CSE 1996
+2
-0.6
The minimum number of interchanges needed to convert the array

89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70

into a heap with the maximum element at the root is
A
0
B
1
C
2
D
3
3
GATE CSE 1996
+2
-0.6
The average number of key comparisons done on a successful sequential search in list of length n is
A
log n
B
$${{n - 1} \over 2}$$
C
$${n \over 2}$$
D
$${{n + 1} \over 2}$$
4
GATE CSE 1994
+2
-0.6
Which one of the following statements is false?
A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find connected components of a graph
C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D
Depth-first search can be used to find connected components of a graph.
GATE CSE Subjects
EXAM MAP
Medical
NEET