# DS | GATE-2007 | PREVIOUS YEAR QUESTIONS| SET-14

DS | GATE-2007 | Data Structures

1. Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering? [ GATE – 2007 ]

a. 1 2 3 4 5 6
b. 1 3 2 4 5 6
c. 1 3 2 4 6 5
d. 3 2 4 1 6 5

DS | GATE-2007 |

2. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is: [ GATE – 2007 ]

a. 2h−1
b. 2h−1 – 1
c. 2h+1– 1
d. 2h+1

DS | GATE-2007 |

3. The maximum number of binary trees that can be formed with three unlabeled nodes is: [ GATE – 2007 ]

a. 1
b. 3
c. 4
d. 5

DS | GATE-2007 |

4. The following postfix expression with single digit operands is evaluated using a stack: [ GATE – 2007 ]

`8 2 3 ^ / 2 3 * + 5 1 * -`

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

a. 6, 1
b. 5, 7
c. 3, 2
d. 1, 5

DS | GATE-2007 |

5. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is: [ GATE – 2007 ]

a. d e b f g c a
b. e d b g f c a
c. e d b f g c a
d. d e f g b c a

6. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table. [ GATE – 2007 ]

a. 8, _, _, _, _, _, 10
b. 1, 8, 10, _, _, _, 3
c. 1, _, _, _, _, _,3
d. 1, 10, 8, _, _, _, 3

7. A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n? [ GATE – 2007 ]

a. 3
b. 4
c. 5
d. 6

1. Consider the following C program segment where CellNode represents a node in a binary tree: [GATE – 2007]

`struct` `CellNode`
`{`
`  struct` `CellNOde *leftChild;`
`  int` `element;`
`  struct` `CellNode *rightChild;`
`};`
`int` `GetValue(struct` `CellNode *ptr)`
`{`
`  int` `value = 0;`
`  if` `(ptr != NULL)`
`  {`
`   if` `((ptr->leftChild == NULL) &&`
`        (ptr->rightChild == NULL))`
`      value = 1;`
`   else`
`      value = value + GetValue(ptr->leftChild)`
`                   + GetValue(ptr->rightChild);`
`  }`
`  return(value);`
`}`

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

a. the number of nodes in the tree
b. the number of internal nodes in the tree
c. the number of leaf nodes in the tree
d. the height of the tree

DS | GATE-2007 |

1. Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:  [GATE – 2007]

a. θ(log2n)
b. θ(log2log2n)
c. θ(n)
d. θ(nlog2n)

1. A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ? [GATE – 2007]

a. d[u] < d[v]
b. d[u] < f[v]
c. f[u] < f[v]
d. f[u] > f[v]

1. When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60? [GATE – 2007]

a. 35
b. 64
c. 128
d. 5040

1. Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty (Q) — returns true if the queue is empty, false otherwise. ii. delete (Q) — deletes the element at the front of the queue and returns its value. iii. insert (Q, i) — inserts the integer i at the rear of the queue. Consider the following function: [GATE – 2007]

void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}

What operation is performed by the above function f ?

a. Leaves the queue Q unchanged
b. Reverses the order of the elements in the queue Q
c. Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order
d. Empties the queue Q

DS | GATE-2007 |

1. Consider the following C program: [GATE – 2007]

#include
#define EOF -1
void push (int); /* push the argument on the stack */
int pop  (void); /* pop the top of the stack */
void flagError ();
int main ()
{         int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if  (isdigit (c) )
push (c);
else if ((c == ‘+’) || (c == ‘*’))
{          m = pop ();
n = pop ();
r = (c == ‘+’) ? n + m : n*m;
push (r);
}
else if (c != ‘ ‘)
flagError ();
}
printf(“% c”, pop ());
}

What is the output of the program for the following input ? 5 2 * 3 3 2 + * +

a.15
b.25
c.30
d.150