1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
A
$$\Theta \,(n)$$
B
$$\Theta \,({\log ^*}n)$$
C
$$\Theta \,({\log\,}n)$$
D
$$\Theta \,(1)$$
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree that has P as its post order traversal. What is the time complexity of the most efficient algorithm for doing this?
A
$$\Theta \,(\log n)$$
B
$$\Theta \,(n)$$
C
$$\Theta \,(n\log n)$$
D
None of the above, as the tree cannot be uniquely determined.
3
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Consider the following functions: F(n) = 2n
G(n) = n!
H(n) = nlogn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
A
f(n) = O (g(n)); g(n) = O(h(n))
B
f(n) = $$\Omega$$ (g(n)); g(n) = O(h(n))
C
g(n) = O (f(n)); h(n) = O(f(n))
D
h(n) = O (f(n)); g(n) = $$\Omega$$ (f(n))
4
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
In the following C function, let n $$ \ge $$ m.
int gcd(n,m)
{
if (n % m == 0) return m;
n = n % m;
return gcd(m,n);
}
How many recursive calls are made by this function?
A
$$\Theta(\log_2n)$$
B
$$\Omega(n)$$
C
$$\Theta(\log_2\log_2n)$$
D
$$\Theta(\sqrt{n})$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP