DataStructures
Question 1 
 There is a main hash table of size 4.
 The 2 least significant bits of a key is used to index into the main hash table.
 Initially, the main hash table entries are empty.
 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.
 First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
 To resolve more collisions, each node of the binary tree is further subdivided into left and right subtrees based on the 4th least significant bit.
 A split is done only if it is needed, i.e., only when there is a collison.
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  10, 9, 6, 7, 5, 13 
B  9, 5, 13, 6, 10, 14 
C  9, 5, 10, 6, 7, 1 
D  5, 9, 4, 13, 10, 7 
The keys are inserted into the main hash table based on their 2 least significant bits.
→ The keys 5, 9, 13 will be inserted in the table with entry “01”.
→ The keys 6 and 10 will be inserted in the table with entry “10”
→ The keys 7 will be inserted in the table with entry “11”
→ Now the entry index 01 has collisions. Check the 3rd least significant bit of the keys 9,5,13. The 3rd least significant bit of the key is 0. Hence, key “9” placed as the left child of “01”. There will be collisions again in between the keys 5 and 13 which need to splitted.
Now check the 4th least significant bit of keys 5 and 13. The key 5 is placed as a left child because the 4th least significant is “0” and the key “13” is placed as right child because its 4th least significant is 1.
→ Now the entry index 10 has a collision. Check the 3rd least significant bit of the keys 10 and 6. The 3rd last significant bit of the key is 0. Hence, “10” is placed as the left child of index “10”.
The 3rd least significant value of “6” is 1. So, we are placed as the right child of index ”10”.
Question 2 
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 ________
A  86 
push(54) ⇒ 54
push(52)=> 54, 52(top)
pop() ⇒ 54 (top)
push(55)==> 54, 55(top)
push(62) ⇒ 54,55,62(top)
s=pop() ⇒ 62 will store into the variable s then s=62
enqueue(21) ⇒ (front) 21(rear)
enqueue(24) ⇒ (Front)21, 24(rear)
dequeue()==> (front) 24(rear)
enqueue(28) ===> (front) 24,28 (rear)
enqueue(32)====>(front) 24,28,32 (rear)
q=dequeue() ⇒ value 24 will store into the variable “q”
q=24
S+q =62+24 =86
Question 3 
 Root of T can never be an articulation point in G.
 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.
 A leaf of T can be an articulation point in G.
 Root of T is an articulation point in G if and only if it has 2 or more children
A  4 
Statement2:
Example1:
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.
Here 2 and 6 are articulation points. If you consider node1 ancestor and node3 descendent, then without passing through from node 2, there exists a path from one node to another node.
Path from node1 to node3 If you consider node5 ancestor and node4 descendent, then without passing through from node6, there exists a path from one node to another node.
Path from node4 to node5
The given statement is not TRUE for all cases. So, the given statement is FALSE.
Statement3: FALSE: Leafs of a DFStree are never articulation points.
Statement4: TRUE: The root of a DFStree is an articulation point if and only if it has at least two children.
Node 2 is an AP because any node from the first subtree (1, 2) is connected to any node from the second subtree (4, 5, 6, 7, 8) by a path that includes node 2. If node 2 is removed, the 2 subtrees are disconnected.
Question 4 
S_{1}:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S_{2}:The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?
A  S_{1}is false and S_{2}is false

B  S_{1}is true and S_{2}is true 
C  S_{1}is true and S_{2}is false 
D  S_{1}is false and S_{2}is true 
The given statements are true, they are well known facts.
 The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
 The sequence of returns corresponds to a postorder traversal of the activation tree.
Question 5 
A  
B  
C  
D 
The time complexity of searching an element in T that is smaller than the maximum element in T is O(1) time.
Example:
Comparing that 5<10 will take only a constant amount of time.
Question 6 
What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A, B, C? Draw all these binary trees.
A  Theory Explanation. 
Question 7 
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 
Postorder:
11, 12, 10, 16, 19, 18, 20, 15
Question 8 
Consider a double hashing scheme in which the primary hash function is h_{1}(k) = k mod 23, and the secondary hash function is h_{2}(k) = 1 + (k mod 19). 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  13 
• K=90
• h_{1}(k) = k mod 23 = 90 mod 23 = 21
• In case of collision, we need to use secondary hash function.
• h_{2}(k) = 1 + (k mod19) = 1 + 90mod19 = 1+14 = 15
• Now (21+15) mod 23 = 36 mod 23 = 13
• So the address is 13.
Question 9 
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  θ(n^{2}) 
C  θ(1) 
D  θ(n) 
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case.
After inserting elements into an empty linked list we have to perform sorting operation.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only.
Let head be the first node of the linked list to be sorted and head Reference be the pointer to head.
The head in MergeSort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^{2}) and heap sort will not be suitable to apply.
Question 10 
Consider the following C program.
#includeint main () { int a [4] [5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}}; printf (“%d\n”, *(*(a+**a+2) +3)); return (0); }
The output of the program is _______.
A  19 
#include
int main()
{
int a[4][5] = { {1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20}
};
printf("%d\n",a); //880 (consider base address = 880)
printf("%d\n",*a); //880
printf("%d\n",**a); //1
printf("%d\n",**a+2); //3
printf("%d\n",a+**a+2); //940
printf("%d\n",*(a+**a+2));//940
printf("%d\n",*(a+**a+2)+3);//952
printf("%d\n",*(*(a+**a+2)+3));//19
return 0;
}
Question 11 
What is the worst case time complexity of inserting n^{2} elements into an AVLtree with n elements initially?
A  θ(n^{4})

B  θ(n^{2})

C  θ(n^{3}) 
D  θ(n^{2} log n) 
In question they asked about n^{2} elements.
So, In worst case it will take o(n^{2} log n) time.
Question 12 
Let G = (V,E) be a directed, weighted graph with weight function w:E → R. For some function f:V → R, for each edge (u,v) ∈ E, define w'(u,v) as w(u,v) + f(u)  f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”.
A  if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G 
B  if and only if ∀u ∈ V, f(u) is positive

C  if and only if ∀u ∈ V, f(u) is negative 
D  for every f: V→R 
Question 13 
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  θ(log n) 
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is log n, hence O(log n+k).
Question 14 
Consider the array representation of a binary minheap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
A  511 
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2.
So, we have to subtract from the total elements
= 5121
= 511
Question 15 
Consider the following statements:
 (i) Firstinfirst out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Lastinfirstout type of computations are efficiently supported by QUEUES.
Which of the following is correct?
A  (ii) and (iii) are true 
B  (i) and (ii) are true 
C  (iii) and (iv) are true 
D  (ii) and (iv) are true 
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer: A
Question 16 
An advantage of chained hash table (external hashing) over the open addressing scheme is
A  Worst case complexity of search operations is less? 
B  Space used is less 
C  Deletion is easier 
D  None of the above 
Question 17 
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?
A  1 
B  3 
C  7 
D  8 
a, b, c are going to unbalance.
Question 18 
Which of the following sequences denotes the post order traversal sequence of the tree of question 14?
A  f e g c d b a 
B  g c b d a f e 
C  g c d b f e a 
D  f e d g c b a 
Left → Right → Root
g c d b f e a
Question 19 
The minimum number of interchanges needed to convert the array
89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70
into a heap with the maximum element at the root is
A  0 
B  1 
C  2 
D  3 
Question 20 
A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left subtree and right subtree of the root respectively is
A  (4, 7) 
B  (7, 4) 
C  (8, 3) 
D  (3, 8) 
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
Question 21 
A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.
A  61 52 14 17 40 43 
B  2 3 50 40 60 43 
C  10 65 31 48 37 43 
D  81 61 52 14 41 43 
E  17 77 27 66 18 43 
Question 22 
The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?
A  Singly linked list 
B  Doubly linked list 
C  Circular doubly linked list 
D  Array implementation of list 
Question 23 
Which of the following is essential for converting an infix expression to the postfix from efficiently?
A  An operator stack 
B  An operand stack 
C  An operand stack and an operator stack 
D  A parse tree 
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
Question 24 
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output?
A  5 3 1 2 4 7 8 6 
B  5 3 1 2 6 4 8 7 
C  5 3 2 4 1 6 7 8 
D  5 3 1 2 4 7 6 8 
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Question 25 
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
A  nonincreasing order 
B  nondecreasing order 
C  strictly increasing order 
D  strictly decreasing order 
Question 26 
Match the pairs in the following questions:
(a) A heap construction (p) Ω(n log_{10} n) (b) Constructing Hash table with linear probing (q) O(n) (c) AVL Tree construction (r) O(n^{2}) (d) Digital trie construction (s) O(n log_{10} n)
A  (a)  (q), (b)  (r), (c)  (s), (d)  (p) 
Constructing Hash table with linear probing  O(n^{2}
AVL tree construction  O(n log_{10} n)
Digital trie construction  Ω(n log_{10} n)
Question 27 
Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,
A  Equal to the number of ways of multiplying (n+1) matrices. 
B  Equal to the number of ways of arranging n out of 2n distinct elements. 
C  
D  Equal to n! 
E  Both (A) and (C). 
Here, both options A and C are true as option A corresponds to n multiply operations of (n+1) matrices, the no. of ways for this is again given by the n^{th} catalan number.
Question 28 
Choose the correct alternatives (More than one may be correct).
The total external path length, EPL, of a binary tree with n external nodes is, EPL = ∑_{w}Iw, where I_{w} is the path length of external node w),A  ≤ n^{2} always. 
B  ≥ n log_{2} n always. 
C  Equal to n^{2} always. 
D  O(n) for some special trees. 
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 29 
Which of the following statements is false?
A  A tree with a n nodes has (n – 1) edges 
B  A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results 
C  A complete binary tree with n internal nodes has (n + 1) leaves 
D  Both B and C 
D: The maximum no. of nodes in a binary tree of height h is 2^{h+1}  1.
h=2 ⇒ 2^{3}  1 ⇒ 7
Question 30 
A complete nary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete nary tree, the number of leaves in it is given by
A  x(n1) + 1 
B  xn  1 
C  xn + 1 
D  x(n+1) 
Let no. of leaf nodes = L
Let n_{t} be total no. of nodes.
So, L+x = n_{t} (I)
Also for nary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = n_{t} (II)
So, equating (I) & (II),
L+x = nx+1
L = x(n1) + 1
Question 31 
Let A be a two dimensional array declared as follows:
A: array [1 ... 10] [1 ... 15] of integer;
Assuming that each integer takes one memory location, the array is stored in rowmajor order and the first element of the array is stored at location 100, what is the address of the element a[i][j]?
A  15i + j + 84 
B  15j + i + 84 
C  10i + j + 89 
D  10j + i + 89 
100 + 15 * (i1) + (j1)
= 100 + 15i  15 + j  1
= 15i + j + 84
Question 32 
Faster access to nonlocal variables is achieved using an array of pointers to activation records called a
A  stack 
B  heap 
C  display 
D  activation tree 
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for nonlocal variables but may be complicated to maintain.
Question 33 
Let p be a pointer as shown in the figure in a single linked list.
What do the following assignment statements achieve?
 q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q
(b) Compute the postfix equivalent of the following Infix expression
3 * log(x+1)  a/2
A  Theory Explanation. 
Question 34 
Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:
Inorder a f b c d g e Postorder a f c g e d b
A  Theory Explanation. 
Question 35 
(a) Derive a recurrence relation of the size of the smallest AVL tree with height h.
(b) What is the size of the smallest AVL tree with height 8.A  Theory Explanation. 
Question 36 
The number of articulation points of the following graph is
A  0 
B  1 
C  2 
D  3 
Total no. of articulation points = 3
Question 37 
(a) In a binary tree, a nil node is defined to be a node with 2 children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.
(b) Draw a minheap that results from insertion of the following elements in order into an initially empty minheap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.
A  Theory Explanation. 
Question 38 
The most appropriate matching for the following pairs
X: depth first search 1: heap Y: breadthfirst search 2: queue Z: sorting 3: stack
is
A  X – 1 Y – 2 Z – 3 
B  X – 3 Y – 1 Z – 2 
C  X – 3 Y – 2 Z – 1 
D  X – 2 Y – 3 Z – 1 
Queue is used in breadthfirst search.
Heap is used in heap.
Question 39 
Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
A  (1 2 (4 5 6 7)) 
B  (1 (2 3 4) 5 6) 7) 
C  (1 (2 3 4) (5 6 7)) 
D  (1 (2 3 NULL) (4 5)) 
(Proper Representation)
Question 40 
Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 ≤ k ≤ n:
reverse(s, 1, k) ; reverse(s, k + 1, n); reverse(s, l, n);
A  Rotates s left by k positions 
B  Leaves s unchanged 
C  Reverses all elements of s 
D  None of the above 
Question 41 
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?
A  LASTIN = LASTPOST 
B  LASTIN = LASTPRE 
C  LASTPRE = LASTPOST 
D  None of the above 
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.
Question 42 
Let G be an undirected graph. Consider a depthfirst traversal of G, and let T be the resulting depthfirst search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?
A  {u, v} must be an edge in G, and u is a descendant of v in T 
B  {u, v} must be an edge in G, and v is a descendant of u in T 
C  If {u, v} is not an edge in G then u is a leaf in T 
D  If {u, v} is not an edge in G then u and v must have the same parent in T 
In DFS after visiting u, there is no child node then back tracking is happen and then visit the node v. There is no need of (u,v) be an edge.
Question 43 
Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack.
(a) To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of 3 operations.
(b) The following postfix expression, containing single digit operands and arithmetic operators + and *, is evaluated using a stack.
5 2 * 3 4 + 5 2 * * +
Show the contents of the stack.
 (i) After evaluating 5 2 * 3 4 +
(ii) After evaluating 5 2 * 3 4 + 5 2
(iii) At the end of evaluation.
A  Theory Explanation is given below. 
Dequeue → reverse, pop, reverse
(b) (i) After evaluating 5 2 * 3 4 +
Sol:
7(3+4) 10(5*2)
(ii) After evaluating 5 2 * 3 4 + 5 2
Sol:
25(5*5) 7(3+4) 10(5*2)
(iii) At the end of evaluation
Sol: 80
Question 44 
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is
A  i1 
B  ⌊i/2⌋ 
C  ⌈i/2⌉ 
D  (i+1)/2 
Left Child is at index: 2i
Right child is at index: 2*i+1
Question 45 
Consider an undirected unweighted graph G. Let a breadthfirst traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadthfirst traversal, which of the following statements is correct?
A  d(r,u) 
B  d(r,u)>d(r,v) 
C  d(r,u)≤d(r,v) 
D  None of the above 
Question 46 
What is the minimum number of stacks of size n required to implement a queue of size n?
A  One 
B  Two 
C  Three 
D  Four 
Question 47 
Consider the following three C functions:
[PI] int*g(void) { int x = 10; return(&x); } [P2] int*g(void) { int*px; *px = 10; return px; } [P3] int*g(void) { int*px; px = (int *) malloc(sizeof(int)); *px = 10; return px; }
Which of the above three functions are likely to cause problems with pointers?
A  Only P3 
B  Only P1 and P3 
C  Only P1 and P2 
D  P1, P2 and P3 
[P2] → It will cause problem because px is in int pointer that is not assigned with any address and we are doing dereferencing.
[P3] → It will work because memory will be stored in px that can be use further. Once function execution completes this will exist in Heap.
Question 48 
(a) Insert the following keys one by one into a binary search tree in the order specified.
15, 32, 20, 9, 3, 25, 12, 1
Show the final binary search tree after the insertions.
(b) Draw the binary search tree after deleting 15 from it.
(c) Complete the statements S1, S2 and S3 in the following function so that the function computes the depth of a binary rooted at t.
typedef struct tnode{ int key; struct tnode *left, *right; } *Tree; int depth(Tree t) { int x,y; it (t == NULL) return0; x=depth(t → left); S1: ____________; S2: if(x>y) return _____________: S3: else return _____________; }
A  Theory Explanation is given below. 
Question 49 
A  log n 
B  n/2 
C  (log_{2})^{n}  1 
D  n 
Question 50 
The results returned by function under valueresult and reference parameter passing conventions
A  Do not differ 
B  Differ in the presence of loops 
C  Differ in all cases 
D  May differ in the presence of exception 