GATE CSE 2008 | GATE CSE Year Wise Previous Years Questions

GATE CSE

PREVIOUS NEXT

GATE CSE 2008

MCQ (Single Correct Answer)

-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

$$\Theta (n)$$

$$\Theta (m)$$

$$\Theta (n+m)$$

$$\Theta (mn)$$

GATE CSE 2008

MCQ (Single Correct Answer)

-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

$$\Theta \,(n)$$

$$\Theta \,({\log ^*}n)$$

$$\Theta \,({\log\,}n)$$

$$\Theta \,(1)$$

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Consider the following functions: F(n) = 2ⁿ
G(n) = n!
H(n) = n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

f(n) = O (g(n)); g(n) = O(h(n))

f(n) = $$\Omega$$ (g(n)); g(n) = O(h(n))

g(n) = O (f(n)); h(n) = O(f(n))

h(n) = O (f(n)); g(n) = $$\Omega$$ (f(n))

GATE CSE 2008

MCQ (Single Correct Answer)

-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?

$$\Theta \,(\log n)$$

$$\Theta \,(n)$$

$$\Theta \,(n\log n)$$

None of the above, as the tree cannot be uniquely determined.

PREVIOUS NEXT

GATE CSE Papers

2024