DS | GATE-2012 | PREVIOUS YEAR QUESTIONS| SET-9

Set-13 DS GATE-2008

DS | GATE-2012 | Data Structures

  1. The worst case running time to search for an element in a balanced binary search tree with n2n elements is : [GATE – 2012]

a. Θ (n log n)
b. Θ (n2n)
c. Θ (n)
d. Θ (log n)

Answer : c)
DS | GATE-2012 | Data Structures


  1. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is : [GATE – 2012]

a. T(n) = 2T(n – 2) + 2
b. T(n) = 2T(n – 1) + 1
c. T(n) = 2T(n – 1) + n
d. T(n) = 2T(n/2) + 1

Answer : b)


  1. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are : [GATE – 2012]

a. full: (REAR+1)mod n == FRONT
empty: REAR == FRONT

b. full: (REAR+1)mod n == FRONT
empty: (FRONT+1) mod n == REAR

c. full: REAR == FRONT
empty: (REAR+1) mod n == FRONT

d. full: (FRONT+1)mod n == REAR
empty: REAR == FRONT

Answer : a)
DS | GATE-2012 |


  1. The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to : [GATE – 2012]

int height (treeptr n)
 {
if (n == NULL)
return -1;
if (n → == NULL)
return o;
else return [B1]; //box 1
else
{
h1 = height (n→ left);
if (n → right == NULL )
return (1+ h1);
else
{
h2 = height (n → right);
return [B2]; // box 2
}
}}

Compute a height of binary tree rooted at the tree pointer of the root. ________ The appropriate expression for the two boxes B1 and B2 are:

a. B1: (1+height(n→right))
B2: (1+max(h1,h2))

b. B1: (height(n→right))
B2: (1+max(h1,h2))

c. B1: height(n→right)
B2: max(h1,h2)

d. B1: (1+ height(n→right))
B2: max(h1,h2)

Answer : a)
DS | GATE-2012 |


Back to GATE-HOME


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *