1
GATE CSE 2005
+2
-0.6
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements '1' and '7' are inserted in the heap in that order, The level order traversal of the heap after the insertion of the elements is:
A
10, 8, 7, 5, 3, 2, 1
B
10, 8, 7, 2, 3, 1, 5
C
10, 8, 7, 1, 2, 3, 5
D
10, 8, 7, 3, 2, 1, 5
2
GATE CSE 2005
+2
-0.6
Consider the following C - function:
double foo(int n){
int i;
double sum;
if(n == 0) return 1.0;
sum = 0.0;
for (i = 0; i < n; i++){
sum += foo(i);
}
return sum;
}
The space complexity of the above function is:
A
O(1)
B
O(n)
C
O(n!)
D
O(nn)
3
GATE CSE 2004
+2
-0.6
What does the following algorithm approximate?
(Assume m > 1, $$\in > 0$$)
x = m;
y = 1;
while(x - y > ε){
x = (x + y) / 2;
y = m/x;
}
print(x);

A
log m
B
m2
C
m1/2
D
m1/3
4
GATE CSE 2004
+2
-0.6
Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is O(m). Consider the following program fragment written in a C like language:
counter = 0;
for(i = 1; i <= n; i++){
if(A[i]==1){
counter++;
}else{
f(counter); counter = 0;
}
}
The complexity of this program fragment is
A
$$\Omega ({n^2})$$
B
$$\Omega (n\,\log n)\,and\,O({n^2})$$
C
$$\theta (n)$$
D
$$O(n)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET