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
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)$$
4
GATE CSE 2004
+2
-0.6
The time complexity of the following C function is (assume n > 0)
int recursive(int n){
if(n == 1){
return (1);
}
return (recursive(n - 1) + recursive(n - 1));
}
A
O(n)
B
O(n log n)
C
O(n2)
D
O(2n)
GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination