GATE CSE 2008 | GATE CSE Year Wise Previous Years Questions

PREVIOUS NEXT

GATE CSE 2008

MCQ (Single Correct Answer)

-0.3

Which of the following is TRUE?

The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)

The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)

The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)

The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

O(Logn)

O(n)

O(nLogn)

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

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Which of the following statements is TRUE?

I, II and IV are inorder sequences of three different BSTs

I is a preorder sequence of some BST with 439 as the root

II is an inorder sequence of some BST where 121 is the root and 52 is a leaf

IV is a postorder sequence of some BST with 149 as the root

GATE CSE 2008

MCQ (Single Correct Answer)

-0.3

A clustering index is defined on the fields which are of type

non-key and ordering

non-key and non-ordering

key and ordering

key and non-ordering

PREVIOUS NEXT

GATE CSE Papers

All year-wise previous year question papers

2026