Data Structures

A Young tableau is a 2D array of integers
increasing from left to right and from top to bottom.
Any unfilled entries are marked with ∞, and hence
there cannot be any entry to the right of, or below a
∞. The following Young tableau consists of unique
entries.

When an element is removed from a Young
tableau, other elements should be moved into its
place so that the resulting table is still a Young
tableau (unfilled entries may be filled with a ∞).
The minimum number of entries (other than 1) to
be shifted, to remove 1 from the given Young
tableau is    .

Consider the following two C code segments. Y
and X are one and two dimensional arrays of size n
and n×n respectively, where 2 ≤n≤10. Assume that
in both code segments, elements of Y are initialized
to 0 and each element X[i][j] of array X is
initialized to i+j. Further assume that when stored
in main memory all elements of X are in same main
memory page frame.

Code segment 1:
// initialize elements of Y to 0
// initialize elements of X[i][j] of X to i+j
for (i=0; i<n; i++)
Y[i] += X[0][i];
Code segment 2:
// initialize elements of Y to 0
// initialize elements of X[i][j] of X to i+j
for (i=0; i<n; i++)
Y[i] += X[i][0];
Which of the following statements is/are correct?

S1: Final contents of array Y will be same in both
code segments
S2: Elements of array X accessed inside the for loop
shown in code segment 1 are contiguous in main
memory
S3: Elements of array X accessed inside the for loop
shown in code segment 2 are contiguous in main
memory

• (a)Only S2 is correct
• (b)Only S3 is correct
• (c)Only S1 and S2 are correct
• (d)Only S1 and S3 are correct

Suppose c = ⟨c[0], ..., c[k-1]⟩ is an array of length k,
where all the entries are from the set {0,1}. For any
positive integers a and n, consider the following
pseudocode.
DOSOMETHING (c, a, n)
z←1
for i←0 to k-1
do z←z2 mod n
if c[i]=1
then z←(z×a) mod n
return z
If k = 4, c = ⟨1, 0, 1, 1⟩, a = 2, and n = 8
then the output of DO SOMETHING (c, a, n) is

.

DATA STRUCTURE

Consider the following code snippet in C language
that computes the number of nodes in a non-empty
singly linked list pointed to by the pointer variable
head.
struct node{
int elt;
struct node *next;
}
int getListSize (struct node *head)
{
if( El ) return 1;
return E2;
}
Which one of the following options gives the
correct replacements for the expressions E1 and
E2?

• (a)E1: head == NULL E2: 1 + getListSize(head)
• (b)E1: head->next == NULL E2: 1 + getListSize(head->next)
• (c)E1: head == NULL E2: 1 + getListSize(head->next)
• (d)E1: head->next == NULL E2: 1 + getListSize(head)

Let LIST be a datatype for an implementation of
linked list defined as follows:
typedef struct list {
int data;
struct list *next;
} LIST;

Suppose the program has created two linked lists,
L1 and L2, whose contents are given in the figure
below (code for creating L1 and L2 is not
provided here). L1 contains 9 nodes, and L2
contains 7 nodes.
Consider the following C program segment that
modifies the list L1. The number of nodes in L1

int find (int query, LIST *list) {
while (list != NULL){
if(list->data == query) return 1;
list = list->next;
}
return 0;
}
int main () {
... ... ...
ptr1=L1; ptr2=L2;
while (ptr1->next != NULL){
query = ptr1->next->data;
if (find (query, L2))
ptr1->next = ptr1->next->next;
else ptr1 = ptr1->next;
}
... ... ...
return 0;
}

Let SLLdel be a function that deletes a node in a
singly-linked list given a pointer to the node and a
pointer to the head of the list. Similarly, let DLLdel
be another function that deletes a node in a doubly-
linked list given a pointer to the node and a pointer to
the head of the list.
Let n denote the number of nodes in each of the linked
lists. Which one of the following choices is TRUE
about the worst-case time complexity of SLLdel and
DLLdel?

• (a)SLLdel is O(1) and DLLdel is O(n).
• (b)Both SLLdel and DLLdel are O(log(n)).
• (c)Both SLLdel and DLLdel are O(1).
• (d)SLLdel is O(n) and DLLdel is O(1). DATA STRUCTURE

Consider the problem of reversing a singly linked
list. To take an example, given the linked list below,

the reversed linked list should look like,

Which one of the following statements is TRUE
about the time complexity of algorithms that solve
the above problem in O(1) space?

• (a)The best algorithm for the problem takes θ(n) time in the worst case.
• (b)The best algorithm for the problem takes θ(nlogn) time in the worst case.
• (c)The best algorithm for the problem takes θ(n2) time in the worst case.
• (d)It is not possible to reverse a singly linked list in O(1) space.

Consider the following ANSI C program:
#include <stdio.h>
#include <stdlib.h>
struct Node{
int value;
struct Node *next;};
int main(){
struct Node *boxE, *head, *boxN; int index = 0;
boxE = head=(struct Node*)malloc(sizeof(struct
Node));
head→value = index;
for (index = 1; index <= 3; index++)
{
boxN = (struct Node *) malloc(sizeof(struct Node));
boxE →next = boxN;
boxN→va1ue = index;
boxE = boxN:

• (a)It dereferences an uninitialized pointer that may result in a run-time error.
• (b)It has a missing return which will be reported as an error by the compiler.
• (c)Upon execution, the program creates a linked list of five nodes.
• (d)Upon execution, the program goes into an infinite loop.

What is the worst case time complexity of inserting n
elements into an empty linked list, if the linked list
needs to be maintained in sorted order?

• (a)Θ(n log n)
• (b)Θ(n2 )
• (c)Θ(1).
• (d)Θ(n)

A queue is implemented using a non-circular singly
linked list. The queue has a head pointer and a tail
pointer, as shown in the figure. Let n denote the
number of nodes in the queue. Let 'enqueue' be
implemented by inserting a new node at the head, and
'dequeue' be implemented by deletion of a node from
the tail.

Which one of the following is the time complexity of
the most time-efficient implementation of 'enqueue'
and 'dequeue, respectively, for this data structure?

• (a)θ(1), θ(1)
• (b)θ(1), θ(n)
• (c)θ(n), θ(1)
• (d)θ(n), θ(n) } for (index = 0; index <= 3; index++) { printf("Value at index %d is %d\n", index, head- >value); head = head→next; printf("Value at index %d is %d\n", index+1, head→value); } } DATA STRUCTURE

Consider the C code fragment given below.
typedef struct node {
int data;
node* next ;
} node;
void join (node* m, node* n) {
node* p=n ;
while (p->next ! =NULL){
p = p -> next ;
}
p-> next = m;
}
Assuming that m and n point to valid NULL-
terminated linked lists, invocation of join will

• (a)append list m to the end of list n for all inputs.
• (b)either cause a null pointer to dereference or append list m to the end of list n.
• (c)cause a null pointer to dereference for all inputs.
• (d)append list n to the end of list m for all inputs.

N items are stored in a sorted doubly linked list.
For a delete operation, a pointer is provided to the
record to be deleted. For a decrease-key operation,
a pointer is provided to the record on which the
operation is to be performed.
An algorithm performs the following operations on
the list in this order:
Θ(N) delete, O(logN) insert, O(logN) find and
Θ(N)decrease-key . What is the time complexity of
all these operations put together?

• (a)O(log2N)
• (b)O(N)
• (c)O(N2)
• (d)O(N2logN)

An unordered list contains n distinct elements. The
number of comparisons to find an element in this list
that is neither maximum nor minimum is :

• (a)O(nlogn)
• (b)O(n)
• (c)O(logn)
• (d)O(1)

The following C function takes a singly-linked list as
input argument. It modifies the list by moving the last
element to the front of the list and returns the
modified list. Some part of the code is left blank.
Choose the correct alternative to replace the blank
line.
typedef struct node

{
int value;
struct node *next;
}Node;
Node *move_to_front(Node *head)
{
Node *p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
return head;
}

• (a)q = NULL; p→next = head; head = p;
• (b)q→next = NULL; head = p; p→next = head;
• (c)head = p; p→next = q; q→next = NULL;
• (d)q→next = NULL; p→next = head; head = p; DATA STRUCTURE

The following C function takes a singly-linked list
of integers as a parameter and rearranges the
elements of the list. The function is called with the
list containing the integers 1,2,3,4,5,6,7 in the given
order. What will be the contents of the list after the
function completes execution?
struct node {
int value;
struct node *next;
};

void rearrange (struct node *list){
struct node *p, *q;
int temp;
if (!list || !list->next) return;

p = list;
q = list->next;
while (q) {
temp = p->value;
p->value = q->value;
q->value = temp;

p = q->next;
q = p ? p->next : 0;
}
}

• (a)1,2,3,4,5,6,7
• (b)2,1,4,3,6,5,7
• (c)1,3,2,5,4,7,6
• (d)2,3,4,5,6,7,1

Consider a stack S and a queue Q. Both of them are
initially empty and have the capacity to store ten
elements each. The elements 1,2,3,4, and 5 arrive
one by one, in that order. When an element arrives,
it is assigned either to S (pushed on S ) or to Q
(enqueued to Q ). Once all the five elements are
stored, the output is generated in two steps. First,
stack S is emptied by popping all elements. Then
queue Q is emptied by dequeueing all elements.
The output obtained by following this process is
43125 .
Given the output, the objective is to predict whether
an element was assigned to S or Q.
Which of the following options is/are possible valid
assignment(s) of the elements?
Note: In the options, the notation xS denotes that
element x was assigned to S and yQ denotes that
element y was assigned to Q.

• (a)1S,2Q,3S,4S,5Q
• (b)1Q,2Q,3S,4S,5Q
• (c)1Q,2Q,3Q,4S,5S
• (d)1S,2S,3S,4Q,5Q

Consider the following sequence of operations on
an empty stack.
push(54); push(52); pop(); push(55); push(62); s =
pop();
Consider the following sequence of operations on
an empty queue.
enqueue (21); enqueue (24); dequeue (); enqueue
(28); enqueue (32); q = dequeue();
The value of s +q is
.
We maintain exactly two external pointers FRONT
and REAR pointing to the front node and the rear
node of the queue, respectively. Which of the
following statements is/are CORRECT for such a
circular queue, so that insertion and deletion
operations can be performed in O(1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

• (a)I only
• (b)II only
• (c)Both I and II
• (d)Neither I nor II

A circular queue has been implemented using a
singly linked list where each node consists of a
value and a single pointer pointing to the next node.
DATA STRUCTURE

The maximum possible number of iterations of the
while loop in the algorithm is
.

A queue is implemented using an array such that
ENQUEUE
and
DEQUEUE
operations
are
performed efficiently. Which one of the following
statements is CORRECT (n refers to the number of
items in the queue)?
Both operations can be performed in O(1) time.

• (a)Both operations can be performed in O(1) time
• (b)At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
• (c)The worst case time complexity for both operations will be Ω(n)
• (d)Worst case time complexity for both operations will be Ω(logn)

Let Q denote a queue containing sixteen numbers and
S be an empty stack. Head(Q) returns the element at
the head of the queue Q without removing it from Q.
Similarly Top(S) returns the element at the top of S
without removing it from S. Consider the algorithm
given below.

The result evaluating the postfix expression
10 5+60 6/*8-is

• (a)248
• (b)213
• (c)142
• (d)71

Consider the C program below
#include <stdio.h>
int *A, stkTop;
int stkFunc (int opcode, int val)
{
static int size=0, stkTop=0;
switch (opcode) {
case -1: size = val; break;
case 0: if (stkTop< size )
A[stkTop++]=val; break;
default: if (stkTop) return A[--stkTop];
}
return -1;
}
int main()
{
int B[20]; A=B; stkTop = -1;
stkFunc (-1, 10);
stkFunc (0, 5);
stkFunc (0, 10);
printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0));
}
The value printed by the above program is

.

Suppose a stack implementation supports an
instruction REVERSE, which reverses the order of
elements on the stack, in addition to the PUSH and
POP instructions. Which one of the following
statements is TRUE (with respect to this modified
stack)?

• (a)A queue cannot be implemented using this stack.
• (b)A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
• (c)A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
• (d)A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

The recurrence relation capturing the optimal
execution time of the Towers of Hanoi problem with
n discs is

• (a)T(n) = 2T(n - 2) + 2
• (b)T(n)= 2T(n - 1) + n
• (c)T(n)= 2T(n/2) + 1
• (d)T(n)= 2T(n - 1) + 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

• (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 DATA STRUCTURE

The following postfix expression with single digit
operands is evaluated using a stack:
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

An implementation of a queue Q, using two stacks
S1 and S2, is given below:
void insert (Q, x) {
push(S1, x);

An Abstract Data Type (ADT) is:

• (a)same as an abstract class
• (b)a data type that cannot be instantiated
• (c)a data type for which only the operations defined on it can be used, but none else
• (d)All of the above

The height of a binary tree is the number of edges
in the longest path from the root to a leaf in the tree.
The maximum possible height of a full binary tree
with 23 nodes is
. (answer in integer)

The following sequence corresponds to the
preorder traversal of a binary search tree
T: 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77 .
The position of the element 60 in the post-order
traversal of T is
.

The set T represents various traversals over binary
tree. The set S represents the order of visiting nodes
during a traversal

T
S
I : Inorder
L: left subtree, node, right
subtree
II : Preorder
M: node, left subtree, right
subtree
III : Postorder
N :  left  subtree,  right
subtree, node
Which one of the following is the correct match
from T to S?

• (a)1-L, II-M, III - N
• (b)I-M, II-L, III - N
• (c)I-N, II-M, III - L
• (d)I-L, II-N, III - M

Consider a binary search tree (BST) with n leaf nodes
(n > 0). Given any node V, the key present in the node
is denoted as Val(V). All the keys present in the given
BST are distinct. The keys belong to the set of real
numbers.

For a node V, let Suc (V) denote the node that is its
inorder successor. If a node V does not have an
inorder successor, then Suc (V) is NULL. As there are
no duplicates, if Suc (V) is not NULL, then Val(V) <
Val(Suc(V)).
Corresponding to every leaf node L1 that has a non-
NULL Suc (Li), a new key ki with the following
property is to be inserted into the BST.
Val(Li) <ki < Val(Suc(Li))
Let K represent the list of all such new keys to be
inserted into the BST.
Which of the following statements is/are true?

• (a)K cannot have any duplicates
• (b)K will have at least one element
• (c)After inserting all keys from K, the height of the BST can increase at most by one
• (d)Number of nodes in the BST will double after inserting all keys from K

Consider the C function foo and the binary tree
shown

DATA STRUCTURE

typedef struct node {
int val;
struct node *left, *right;
} node;
int foo(node *p)

{
int retval;
if (p == NULL)
return 0;

else{
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
obtained by doing DFS in a connected undirected
graph G.
Which of the following options is/are correct?

• (a)Root of T is an articulation point in G if and only if it has 2 or more children.
• (b)A leaf of T can be an articulation point in G.
• (c)Root of T can never be an articulation point in G.
• (d)If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u. } When foo is called with a pointer to the root node of the given binary tree, what will it print?
• (a)3 8 5 13 11 10
• (b)3 5 8 10 11 13
• (c)3 8 16 13 24 50
• (d)3 16 8 50 24 13

Suppose a binary search tree with 1000 distinct
elements is also a complete binary tree. The tree is
stored using the array representation of binary heap
trees. Assuming that the array indices start with 0,
the 3rd largest element of the tree is stored at index

Let H be a binary min-heap consisting of n
elements implemented as an array. What is the
worst case time complexity of an optimal algorithm
to find the maximum element in H '?

• (a)Θ(n)
• (b)Θ(1)
• (c)Θ(logn)
• (d)Θ(n log n)

An articulation point in a connected graph is a
vertex such that removing the vertex and its
incident edges disconnects the graph into two or
more connected components. Let T be a DFS three

Consider a complete binary tree with 7 nodes. Let A
denote the set of first 3 elements obtained by
performing Breadth-First Search (BFS) starting from
the root. Let B denote the set of first 3 elements
obtained by performing Depth-First Search (DFS)
starting from the root.The value of |A – B| is

A binary search T contains n distinct elements. What
is the time complexity of picking an element in T that
is smaller than the maximum element in T?

• (a)Θ(n)
• (b)Θ(log n)
• (c)Θ(n log n)
• (d)Θ(1)

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.

• (a)Θ(n log k)
• (b)Θ(log n + k)
• (c)Θ(k log n)
• (d)Θ(logn) DATA STRUCTURE

What is the worst case time complexity of inserting
n2 elements into an AVL-tree with n elements
initially?

• (a)Θ(n4)
• (b)Θ(n2)
• (c)Θ(n3)
• (d)Θ(n2 log n)

The preorder traversal of a binary search tree is 15,
10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder
traversal of the tree?

• (a)20, 19, 18, 16, 15, 12, 11, 10
• (b)11, 12, 10, 16, 19, 18, 20, 15
• (c)10, 11, 12, 15, 16, 18, 19, 20
• (d)19, 16, 18, 20, 11, 12, 10, 15

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)

The pre-order traversal of a binary search tree is
given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.
Then the post-order traversal of this tree is:

• (a)2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
• (b)2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
• (c)7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
• (d)7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

Let T be a binary search tree with 15 nodes. The
minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.

• (a)4 and 15 respectively
• (b)3 and 14 respectively
• (c)4 and 14 respectively
• (d)3 and 15 respectively

A binary tree T has 20 leaves. The number of nodes
in T having two children is
.

• (a)19
• (b)20
• (c)21
• (d)22

An operator delete(i) for a binary heap data structure
is to be designed to delete the item in the i-th node.
Assume that the heap is implemented in an array and
i refers to the i-th index of the array. If the heap tree
has depth d (number of edges on the path from the
root to the farthest leaf), then what is the time
complexity to re-fix the heap efficiently after the
removal of the element?

• (a)O(1)
• (b)O(d) but not O(1)
• (c)O(2d) but not O(d)
• (d)O(d2d) but not O(2d)

A complete binary min-heap is made by including
each integer in [1, 1023] exactly once. The depth of a
node in the heap is the length of the path from the root
of the heap to that node. Thus, the root is at depth 0.
The maximum depth at which integer 9 can appear is

The number of ways in which the numbers 1, 2, 3, 4,
5, 6, 7 can be inserted in an empty binary search tree,
such  that  the  resulting  tree  has  height  6,  is

DATA STRUCTURE

Note: The height of a tree with a single node is 0.
[This question was originally a Fill-in-the-Blanks
question]

• (a)2
• (b)4
• (c)64
• (d)32

Consider the following New-order strategy for
traversing a binary tree:
• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;
The New-order traversal of the expression tree
corresponding to the reverse polish expression 3 4
* 5 - 2 ˆ 6 7 * 1 + - is given by:

• (a)+ - 1 6 7 * 2 ˆ 5 - 3 4 *
• (b)- + 1 * 6 7 ˆ 2 - 5 * 3 4
• (c)- + 1 * 7 6 ˆ 2 - 5 * 4 3
• (d)1 7 6 * + 2 5 4 3 * - ˆ -

Consider the following array of elements. 〈89, 19,
50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum
number of interchanges needed to convert it into a
max-heap is

• (a)4
• (b)5
• (c)2
• (d)3

Consider a max heap, represented by the array: 40,
30, 20, 10, 15, 16, 17, 8, 4. Now consider that a
value 35 is inserted into this heap. After insertion,
the new heap is

• (a)40, 30, 20, 10, 15, 16, 17, 8, 4, 35
• (b)40, 35, 20, 10, 30, 16, 17, 8, 4, 15
• (c)40, 30, 20, 10, 35, 16, 17, 8, 4, 15
• (d)40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Consider a binary tree T that has 200 leaf nodes.
Then, the number of nodes in T that have exactly two
children are

• (a)199
• (b)198
• (c)197
• (d)196

The height of a tree is the length of the longest root-
to-leaf path in it. The maximum and minimum
number of nodes in a binary tree of height 5 are

• (a)63 and 6, respectively
• (b)64 and 5, respectively
• (c)32 and 6, respectively
• (d)31 and 5, respectively

While inserting the elements 71, 65, 84, 69, 67, 83 in
an empty binary search tree (BST) in the sequence
shown, the element in the lowest level is

• (a)65
• (b)67
• (c)69
• (d)83

Consider it to rooted n node binary tree represented
using pointers. The best upper bound on the time
required to determine the number of subtrees having
having exactly 4 nodes O(na logb n). Then the value of
a + 10b is

DATA STRUCTURE

• (a)1
• (b)11
• (c)12
• (d)21

A priority queue is implemented as a Max-Heap.
Initially, it has 5 elements. The level-order traversal
of the heap is: 10, 8, 5, 3, 2. Two new elements 1
and 7 are inserted into the heap in that order. The
level-order traversal of the heap after the insertion
of the elements is:

• (a)10, 8, 7, 3, 2, 1, 5
• (b)10, 8, 7, 2, 3, 1, 5
• (c)10, 8, 7, 1, 2, 3, 5
• (d)10, 8, 7, 5, 3, 2, 1

Consider the C function given below. Assume that
the array listA contains n(>0) elements, sorted in
ascending order
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k]) j = k-1;
if (listA[k] <= x) i = k+1;
}
while (i <= j);
if (listA[k] == x) return(k);
else return -1;
}
Which one of the following statements about the
function ProcessArray is CORRECT?

• (a)It will run into an infinite loop when x is not in listA.
• (b)It is an implementation of binary search.
• (c)It will always find the maximum element in listA.
• (d)It will return -11 even when xx is present in listA.

Consider the pseudocode given below. The function
DoSomething() takes as argument a pointer to the
root of an arbitrary tree represented by the
leftMostChild-rightSibling representation. Each node
of the tree is of type treeNode.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL) {
if (tree->leftMostChild == NULL) value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}
DATA STRUCTURE

When the pointer to the root of a tree is passed as
the argument to DoSomething, the value returned
by the function corresponds to the

• (a)number of internal nodes in the tree.
• (b)height of the tree.
• (c)number of nodes without a right sibling in the tree.
• (d)number of leaf nodes in the tree.

Consider the following rooted tree with the vertex
P labelled as root

The preorder traversal sequence of a binary search
tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one
of the following is the postorder traversal sequence
of the same tree?

• (a)10, 20, 15, 23, 25, 35, 42, 39, 30
• (b)15, 10, 25, 23, 20, 42, 35, 39, 30
• (c)15, 20, 10, 23, 25, 42, 35, 39, 30
• (d)15, 10, 23, 25, 20, 35, 42, 39, 30 } 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)

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
compute the height of a binary tree rooted at the tree
pointer root.
int height(treeptr n)
{
if(n == NULL) return -1;
if(n -> left == NULL)
if(n -> right == NULL) return 0;
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}
}

The order in which the nodes are visited during in-
order traversal is

• (a)SQPTRWUV
• (b)SQPTURWV
• (c)SQPTWUVR
• (d)SQPTRUWV

A max-heap is a heap where the value of each parent
is greater than or equal to the values of its children.
Which of the following is a max-heap?

• (a)DATA STRUCTURE
• (b)
• (c)
• (d)
• (a)0
• (b)1
• (c)(n - 1)/2
• (d)n – 1

We are given a set of n distinct elements and an
unlabeled binary tree with n nodes. In how many
ways can we populate the tree with the given set
so that it becomes a binary search tree?

• (a)0
• (b)1
• (c)n!
• (d)1 * 2nCn n+1

In a binary tree with n nodes, every node has an
odd number of descendants. Every node is
considered to be its own descendant. What is the
number of nodes in the tree that have exactly
one child?

What is the maximum height of any AVL-tree with 7
nodes ? Assume that the height of a tree with a single
node is 0.

• (a)2
• (b)3
• (c)4
• (d)5

Consider a binary max-heap implemented using an
array. Which one of the following array represents
a binary max-heap?

• (a){25, 12, 16, 13, 10, 8, 14 }
• (b){(25, 14, 13, 16, 10, 8, 12}
• (c){25, 14, 16, 13, 10, 8, 12}
• (d){25, 14, 12, 13, 10, 8, 16}

Consider a binary max-heap implemented using an
array. What is the content of the array after two delete
operations on

• (a){14, 13. 12. 10, 8}
• (b){14, 12,13, 8, 10}
• (c){14, 13, 8, 12, 10}
• (d){14, 13, 12, 8, 10}

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?

• (a)O(logn)
• (b)O(n)
• (c)O(nlogn)
• (d)none of the above, as the tree cannot be uniquely determined. DATA STRUCTURE

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:

• (a)2h-1
• (b)2h-1-1
• (c)2h+1-1
• (d)2h+1

The maximum number of binary trees that can be
formed with three unlabeled nodes is:

• (a)1
• (b)5
• (c)4
• (d)3

The inorder and preorder traversal of a binary tree
are
Inorder: d b e a f c g
Preorder: a b d e c f g
The postorder traversal of the binary tree is:

• (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

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?

• (a)3
• (b)4
• (c)5
• (d)6

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:

• (a)Θ(log2 n)
• (b)Θ(log2 log2 n)
• (c)Θ(n)
• (d)Θ(n log2 n)

In a binary max heap containing n numbers, the
smallest element can be found in time

• (a)O(n)
• (b)O(log n)
• (c)O(log log n)
• (d)O(1)

A 3-ary max heap is like a binary max heap, but
instead of 2 children, nodes have 3 children. A 3-ary
heap can be represented by an array as follows: The
root is stored in the first location, A[0], nodes in the
next level, from left to right, are stored from A[1] to
A[3]. The nodes from the second level of the tree
from left to right are stored from A[4] onward. An
item x can be inserted into a 3-ary heap containing n
items by placing x in the location A[n] and pushing
it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of
elements in an array representing a 3-ary max heap?

• (a)1, 3, 5, 6, 8, 9
• (b)9, 6, 3, 1, 8, 5
• (c)9, 3, 6, 8, 5, 1
• (d)9, 5, 6, 8, 3, 1

A 3-ary max heap is like a binary max heap, but
instead of 2 children, nodes have 3 children. A 3-ary
heap can be represented by an array as follows: The
DATA STRUCTURE

root is stored in the first location, A[0], nodes in
the next level, from left to right, are stored from
A[1] to A[3]. The nodes from the second level of
the tree from left to right are stored from A[4]
onward. An item x can be inserted into a 3-ary
heap containing n items by placing x in the
location A[n] and pushing it up the tree to satisfy
the heap property.
Suppose the elements 7, 2, 10 and 4 are inserted, in
that order, into the valid 3-ary max heap found in
the previous question . Which one of the following
is the sequence of items in the array representing
the resultant heap?

• (a)10, 7, 9, 8, 3, 1, 5, 2, 6, 4
• (b)10, 9, 8, 7, 6, 5, 4, 3, 2, 1
• (c)10, 9, 4, 5, 7, 6, 8, 2, 1, 3
• (d)10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Postorder traversal of a given binary search tree, T
produces the following sequence of keys:
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can
be the result of an in-order traversal of the tree T?

• (a)9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
• (b)9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
• (c)29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
• (d)95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

A priority queue is implemented as a Max-Heap.
Initially, it has 5 elements. The level-order
traversal of the heap is:10, 8, 5, 3, 2
Two new elements 1 and 7 are inserted into the
heap in that order. The level-order traversal of the
heap after the insertion of the elements is:

• (a)10, 8, 7, 5, 3, 2, 1
• (b)10, 8, 7, 2, 3, 1, 5
• (c)10, 8, 7, 1, 2, 3, 5
• (d)10, 8, 7, 3, 2, 1, 5

How many distinct binary search trees can be
created out of 4 distinct keys?

• (a)5
• (b)14
• (c)24
• (d)42

In a complete k-ary tree, every internal node has
exactly k children. The number of leaves in such a
tree with n internal nodes is:

• (a)nk
• (b)(n - 1)k + 1
• (c)n(k - 1) + 1
• (d)n(k - 1)

Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋
elements each. The time complexity of producing a
sorted list of all these elements is: (Hint: Use a heap
data structure)

• (a)O(nlog log n)
• (b)θ(nlog n)
• (c)Ω(nlog n) 3
• (d)Ω (n2) DATA STRUCTURE

Consider a hash table P[0, 1, ..., 10] that is initially
empty. The hash table is maintained using open
addressing with linear probing. The hash function
used is :
h(x) = (x + 7) mod 11. Consider the following
sequence of insertions performed on
P: 1, 13, 22, 15, 11, 24
Which of the following positions in the hash table
is/are empty after these insertions are performed?
collisions. Let k be the number of keys, m be the
number of slots in the hash table, and k>m.
Which one of the following is the best hashing
strategy to counteract the adversary?

• (a)Division method, i.e., use the hash function h(k) = k mod m
• (b)Universal hashing method.
• (c)Multiplication method, i.e., use the hash function h(k) = ⌊m(kA -⌊kA⌋)⌋ , where A is a carefully chosen constant.
• (d)If k is a prime number, use Division method. Otherwise, use Multiplication method.
• (a)0
• (b)10
• (c)2
• (d)1

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are
inserted into a hash table using the hash function
h(k) = k mod 9. The collisions are resolved by
chaining. After all the keys are inserted, the length
of the longest chain is
.

In a double hashing scheme, h1(k) = k mod 11
and h2(k) = 1 + (k mod 7) are the auxiliary hash
functions. The size m of the hash table is 11. The
hash function for the i-th probe in the open address
table is
[h1(k) + ih2(k)] mod m The following keys are
inserted in the given order: 63, 50, 25, 79, 67, 24.
The slot at which key 24 gets stored is
.
(Answer in integers)

An algorithm has to store several keys generated
by an adversary in a hash table. The adversary is
malicious who tries to maximize the number of
two simple uniform hash functions h1 and h2.
Further suppose our hashing scheme uses h1 for the
odd keys and h2 for the even keys. What is the
expected number of keys in a slot?

• (a)m/n
• (b)n/m
• (c)2n/m
• (d)n/2m

Suppose we are given n keys, m hash table slots, and

Consider a dynamic hashing approach for 4-bit
integer keys:
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to
index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to
resolve collisions, the set of all keys corresponding
to a main hash table. entry is organized as a binary
tree that grows on demand.
5. First, the 3rd least significant bit is used to divide
the keys into left and right subtrees.
6. To resolve more collisions, each node of the
binary tree is further sub-divided into left and right
subtrees based on the 4th least significant bit.
DATA STRUCTURE

7. A split is done only if it is needed, i.e., only
when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key
insertions can cause the above state of the hash
table (assume the keys are in decimal notation)?

• (a)5,9,4,13,10,7
• (b)9,5,10,6,7,1
• (c)10,9,6,7,5,13
• (d)9, 5,13,6,10,14

Consider a double hashing scheme in which the
primary hash function is h1(k) = k mod 23, and
the secondary hash function is h2(k) = 1 +
(kmod19). Assume that the table size is 23. Then
the address returned by probe 1 in the probe
sequence (assume that the probe sequence begins at
probe 0) for key value k=90 is
.

A hash table of length 10 uses open addressing with
hash function h(k) = k mod 10, and linear
probing. After inserting 6 values into an empty hash
table, the table is as shown below

How many different insertion sequences of the key
values using the same hash function and linear
probing will result in the hash table shown above?

• (a)10
• (b)20
• (c)30
• (d)

Which one of the following choices gives a possible
order in which the key values could have been
inserted in the table?

• (a)46, 42, 34, 52, 23, 33
• (b)34, 42, 23, 52, 33, 46
• (c)46, 34, 42, 23, 52, 33
• (d)42, 46, 33, 23, 34, 52

Which one of the following hash functions on
integers will distribute keys most uniformly over 10
buckets numbered 0 to 9 for i ranging from 0 to 2020?

• (a)h(i)= i2 mod 10
• (b)h(i)= i3 mod 10
• (c)h(i)=(11*i2) mod 10
• (d)h(i)=(12*i2) mod 10

Consider a hash table with 9 slots. The hash function
is h(k) = k mod 9. The collisions are resolved by
chaining. The following 9 keys are inserted in the
order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum,
minimum, and average chain lengths in the hash
table, respectively, are

• (a)3,0,and 1
• (b)3,3,and 3
• (c)4,0,and 1
• (d)3,0,and 2

Consider a hash table with 100 slots. Collisions are
resolved using chaining. Assuming simple uniform
DATA STRUCTURE

hashing, what is the probability that the first 3 slots
are unfilled after the first 3 insertions?

• (a)(97 x 97 x 97)/1003
• (b)(99 x 98 x 97)/1003
• (c)(97 x 96 x 95)/1003
• (d)(97 x 96 x 95)/(3! x 1003)

The keys 12,18,13,2,3,23,5 and 15 are inserted
into an initially empty hash table of length 10 using
open addressing with hash function h(k) = k mod
10 and linear probing. What is the resultant hash
table ?

• (a)0 1 2 2 3 2 4 5 1 6 7 8 1 9
• (b)
• (c). 0 1 2 12 3 13 4 2 5 3 6 23 7 5 8 18 9 15
• (d). 0 1 2 12,2 3 13,3,23 4 5 5,15 6 7 8 18 9

Consider a hash table of size seven, with starting
index zero, and a hash function h(x) = (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.

• (a)8, –, –, –, –, –, 10
• (b)1, 8, 10, –, –, –, 3
• (c)1, –, –, –, –, –, 3
• (d)1, 10, 8, –, –, –, 3 0 1 2 12 3 13 4 5 5 6 7 8 18 DATA STRUCTURE