GATE CSE 2008 | GATE CSE Year Wise Previous Years Questions

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

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.

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.3

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

It is the position in a sentential form where the next shift or reduce operation will occur

It is non-terminal whose production will be used for reduction in the next step

It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur

It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found

PREVIOUS NEXT

GATE CSE Papers

2024