GATE CSE 2021 Set 1 | Trees Question 3 | Data Structures

PREVIOUS NEXT

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Consider the following statements.

S₁ : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

S₂ : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

S₁ is true and S₂ is true

S₁ is false and S₂ is true

S₁ is false and S₂ is false

S₁ is true and S₂ is false

GATE CSE 2020

MCQ (Single Correct Answer)

-0.67

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.

$$\Theta \left( {\log n} \right)$$

$$\Theta \left( {\log n + k} \right)$$

$$\Theta \left( {k\log n} \right)$$

$$\Theta \left( {n\log k} \right)$$

GATE CSE 2020

Numerical

-0.67

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

Your input ____

GATE CSE 2019

Numerical

-0.67

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

Your input ____