1
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.
2
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))
3
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)$$
4
GATE CSE 2008
MCQ (Single Correct Answer)
+1
-0.3
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
A
$$\Theta (n)$$
B
$$\Theta (m)$$
C
$$\Theta (n+m)$$
D
$$\Theta (mn)$$
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12