DataStructures
Question 1 
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) _____.
5.54  
1.34  
4.25  
3.82 
A node can be chosen twice and the path from that node to itself will be zero.
∴ Path 1 = 0
Similarly,
Path 2 = 2
Path 3 = 4
Path 4 = 4
Path 5 = 6
Path 6 = 6
Path 7 = 6
Path 8 = 6
∴ Expected value = Σ Path length × Probability of selecting path
= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8
= 1/4 + 1/1 + 3/1 + 0
= 4 + 1/4
= 17/4
= 4.25
Question 2 
Which one of the following is the postorder traversal of the tree?
20, 19, 18, 16, 15, 12, 11, 10
 
11, 12, 10, 16, 19, 18, 20, 15
 
10, 11, 12, 15, 16, 18, 19, 20  
19, 16, 18, 20, 11, 12, 10, 15 
Question 3 
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 4 
option A and option B 
When we are inserting an element in to empty linked list and to perform sorted order list of every element will take O(n^2)
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
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.
Method2:
When we are inserting an element into an empty linked list and to perform a sorted list after inserting all elements will take O(nlogn) time.
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
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 operations.
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 Merge Sort 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.
Note: They are given “needs to be maintained in sorted order” but not given clear conditions to sort an elements.
Question 5 
#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+**a+2) +3));
return (0);
}
The output of the program is _______.
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 6 
In question they asked about n^{2} elements.
So, In worst case it will take o(n^{2} logn) time.
Question 7 
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 logn, hence O(logn+k)
Question 8 
511 
When it performs minimum comparisons it will take Ceil(n/2)
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 9 
1  
2  
3  
4 
In – 8 6 9 4 7 2 5 1 3
Post: 8 9 6 7 4 5 2 3 1→(root)
In: 8 6 9 4 7 2 5→(left subtree) 13→(right subtree)
Question 10 
A queue is implemented using a noncircular 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 timeefficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?
θ(1), θ(1)  
θ(1), θ(n)  
θ(n), θ(1)  
θ(n), θ(n) 
But if we have pointer to the tail of the list in order to delete it, we need the address of the 2^{nd} last node which can be obtained by traversing the list which takes O(n) time.
Question 11 
Let G be a simple undirected graph. Let T_{D} be a depth first search tree of G. Let T_{B} be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to T_{D}.
(A cross edge in G is between two nodes neither of which is an ancestor of the other in T_{D}.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in T_{B}, then ∣i−j∣ = 1.
Which of the statements above must necessarily be true?
I only  
II only  
Both I and II  
Neither I nor II 
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.
There is an edge between B and C too. So here i  j = 1  1 = 0. Hence, False.
Question 12 
80  
81  
82  
83 
> After sorting, pick the minimum element and make it the root of the min heap.
> So, there is only 1 way to make the root of the min heap.
> Now we are left with 6 elements.
> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80
Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .
Question 13 
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 NULLterminated linked lists, invocation of join will
append list m to the end of list n for all inputs.  
either cause a null pointer dereference or append list m to the end of list n.  
cause a null pointer dereference for all inputs.  
append list n to the end of list m for all inputs. 
So have to consider both the cases.
⇾ 1. Lists are not null, invocation of JOIN will append list m to the end of list n.
m = 1, 2, 3
n = 4, 5, 6
After join, it becomes 4, 5, 6, 1, 2, 3, NULL.
⇾ 2. If lists are null, if the list n is empty, and itself NULL, then joining & referencing would obviously create a null pointer issue.
Hence, it may either cause a NULL pointer dereference or appends the list m to the end of list n.
Question 14 
18  
19  
20  
21 
A tree, with 10 vertices, consists n  1, i.e. 10  1 = 9 edges.
Sum of degrees of all vertices = 2(#edges)
= 2(9)
= 18
Question 15 
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. 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.
I only  
II only  
Both I and II  
Neither I nor II 
2. Next pointer of rear points to the front node.
So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
Question 16 
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?
MNOPQR  
NQMPOR  
QMNROP  
POQNMR 
(Do it by option Elimination)
(a) MNOPQR – MNO is not the proper order R must come in between.
(b) NQMPOR – QMP is not the order O is the child of N.
(C) QMNROP – M is not the child of Q, so QMN is false.
(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).
Question 17 
The preorder traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the postorder traversal of this tree is:
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20  
2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12  
7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12  
7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 
From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree.
From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.
From <17, 19, 20>, 19 as root.
Hence, 2,7,6,10,9,8 ,15,17,20,19,16 12 is the postorder traversal.
Question 18 
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efﬁciently. 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  
At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)  
The worst case time complexity for both operations will be Ω(n)  
Worst case time complexity for both operations will be Ω(logn) 
Hence even the worst case time complexity will be O(1) by the use of the Circular queue there won't be any need of shifting in the array.
Question 19 
Consider the following directed graph:
The number of different topological orderings of the vertices of the graph is __________.
7  
9  
8  
6 
It is observed that (a) is the starting vertex & (f) is the final one.
Also observed that c must come after b & e must come after d.
So,
Hence, there are 6 different topological orderings can be derived.
Question 20 
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
P only  
Q only  
Neither P nor Q  
Both P and Q 
Every edge weight is increased by the same value say,
P: Minimum Spanning Tree will not change ABC in both the cases.
Q: Shortest path will change because in 1st figure the path from A to C calculated as ABC but in fig.2, it is AC (Direct path).
Question 21 
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the ith node. Assume that the heap is implemented in an array and i refers to the ith 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ﬁx the heap efﬁciently after the removal of the element?
O(1)  
O(d) but not O(1)  
O(2^{d}) but not O(d)  
O(d 2^{d}) but not O(2^{d}) 
→ Because we first need to find that element, O(n) time
Delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].
**but here, we don't need to find that element, because in delete(i), i is index of that element.
Note: Delete time = O(height) = O(d)
Question 22 
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry W_{ij} in the matrix W.
The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is _________.
12  
13  
14  
15 
x directly connects C to D.
The shortest path (excluding x) from C to D is of weight 12 (CBAD).
Question 23 
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 maximum possible number of iterations of the while loop in the algorithm is _________.
256  
257  
258  
259 
Try to solve it for 3 numbers [1. 2, 3].
Step 1: Initially Queue contains 3 elements so after 5 while loop iterations queue contains 3, 2 and stack contains 1.
Step 2: Now after 3 more while loop iterations, Queue contains 3 and stack contains 1, 2 (TOS = 2).
Step 3: After 1 more while loop iteration, push 3 onto the stack so queue is empty and stack contains 1, 2, 3 {top = 3}.
So, total number of iterations will be 5 + 3 + 1 = 9
i.e., for 3 it is 9 iterations (3*3)
for 4 it is 16 iterations (4*4)
Given: 16 numbers, so 16 * 16 = 256
Question 24 
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the nth vertex in this BFS traversal, then the maximum possible value of n is _________.
31  
32  
33  
34 
For distance 1, max possible value is (3).
Similarly, for distance 2, max value is (7).
So, maximum number of nodes = 2^{(h+1)}  1
For distance 4, 2^{(4+1)}  1 ⇒ 2^{5}  1 ⇒ 32  1 = 31
31 is the last node.
So for distance 4, the maximum possible node will be 31 & minimum will be 16.
Question 25 
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 decreasekey 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) ﬁnd, and Θ(N) decreasekey. What is the time complexity of all these operations put together?
O(log^{2} N)  
O(N)  
O(N^{2})  
Θ(N^{2} logN) 
→ Delete needs O(1) time
→ Insert takes O(N) time
→ Find takes O(N) time
→ Decrease by takes O(N) time
Now number of each operation performed is given, so finally total complexity,
→ Delete = O(1) × O(N) = O(N)
→ Find = O(N) × O(log N) = O(N log N)
→ Insert = O(N) × O(log N) = O(N log N)
→ Decrease key = O(N) × O(N) = O(N^{2})
So, overall time complexity is, O(N^{2}).
Question 26 
A complete binary minheap 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 _________.
8  
9  
10  
11 
This is not possible because it violates a property of complete binary tree.
We have total [0, 1023] elements. It means that
∴ 2^{0} + 2^{1} + 2^{2} + ⋯ + 2^{k} = 1024
Add if 1(2^{(k+1)}1)/(21) [using formula for sum of k terms k+1 in G.P]
= 2^{(k+1)}  1 = 1024  1 = 1023
∴ The level ‘9’ at the depth of 8.
Actually we have 1023 elements, we can achieve a complete binary min heap of depth 9, which would cover all 1023 elements, but the max depth of node 9 can be only be 8.
Question 27 
Consider the following Neworder strategy for traversing a binary tree:
 Visit the root;
 Visit the right subtree using Neworder;
 Visit the left subtree using Neworder;
The Neworder traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5  2 ˆ 6 7 * 1 +  is given by:
+  1 6 7 * 2 ˆ 5  3 4 *  
 + 1 * 6 7 ˆ 2  5 * 3 4  
 + 1 * 7 6 ˆ 2  5 * 4 3  
1 7 6 * + 2 5 4 3 *  ˆ  
Given Reverse Polish Notation as:
3 4 * 5  2 ^ 6 7 * 1 + 
We know Reverse Polish Notation takes Left, Right, Root.
So the expression tree looks like
From the tree, we can write the New Order traversal as: Root, Right, Left.
 + 1 * 7 6 ^ 2  5 * 4 3
Question 28 
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 _________.
Note: The height of a tree with a single node is 0.64  
65  
66  
67 
So to get such tree at each level we should have either maximum or minimum element from remaining numbers till that level. So no. of binary search tree possible is,
1^{st} level  2 (maximum or minimum)
⇓
2^{nd} level  2
⇓
3^{rd} level  2
⇓
4^{th} level  2
⇓
5^{th} level  2
⇓
6^{th} level  2
⇓
7^{th} level  2
= 2 × 2 × 2 × 2 × 2 × 2 × 1
= 2^{6}
= 64
Question 29 
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If E = m and V = n, and the memory size is not a constraint, what is the time complexity of the most efﬁcient algorithm to set the twin pointer in each entry in each adjacency list?
Θ(n^{2})  
Θ(n+m)  
Θ(m^{2})  
Θ(n^{4}) 
Visit every vertex levelwise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.
Question 30 
63 and 6, respectively  
64 and 5, respectively  
32 and 6, respectively
 
31 and 5, respectively 
2^{h+1}  1 = 2^{5+1}  1 = 63
Minimum number of nodes in a binary tree of height h is
h + 1 = 5 + 1 = 6
Question 31 
40, 30, 20, 10, 15, 16, 17, 8, 4, 35  
40, 35, 20, 10, 30, 16, 17, 8, 4, 15  
40, 30, 20, 10, 35, 16, 17, 8, 4, 15  
40, 35, 20, 10, 15, 16, 17, 8, 4, 30 
Heapification:
Array representation of above maxheap is (BFS)
40,35,20,10,30,16,17,8,4,15
Question 32 
19  
20  
21  
22 
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n p1' (i.e., interval) vertices of degree 3
(iv) n 1 edges
∴ By Handshaking theorem,
p×1+1×2+(np1)×3=2(n1)
⇒n=2p1
=39 as p=20
∴ np=19 vertices have exactly two children
Question 33 
Ω(logn)  
Ω(n)  
Ω(nlog n)  
Ω(n^{2}) 
Question 34 
h(i) = i^{2} mod 10
 
h(i) = i^{3} mod 10
 
h(i) = (11 *i^{2}) mod 10
 
h(i) = (12 * i) mod 10 
Question 35 
63 milliseconds, 65535×2^{14}  
63 milliseconds, 65535×2^{16}
 
500 milliseconds, 65535×2^{14}
 
500 milliseconds, 65535×2^{16}

The wrap around time for given link = 1048560 * α. The TCP window scale option is an option to increase the receive window size. TCP allows scaling of windows when wrap around time > 65,535.
==> 1048560 * α. > 65,535*8 bits
==> α = 0.5 sec = 500 mss
Scaling is done by specifying a one byte shift count in the header options field. The true receiver window size is left shifted by the value in shift count. A maximum value of 14 may be used for the shift count value. Therefore maximum window size with scaling option is 65535 × 2^14
.
Question 36 
A younf tableau is a 2D array of integers iniceasing from left to right and from top to bottom. Any unfilled entries are marked with
4  
5  
6  
7 
Question 37 
80  
70  
60  
50 
Question 38 
4  
5  
2  
3 
→ Swap 100 & 15
→ Swap 100 & 50
→ Swap 89 & 100
∴ Total 3 interchanges are needed.
Question 39 
65
 
67
 
69
 
83 
Question 40 
284  
213  
142  
71 
→ '5' is pushed in the stack
→ '+' comes so addition will be done by popping the top two elements in the stackand the result is pushed back into the stack, i.e., 10+5 = 15
→ 60 pushed in the stack
→ 6 pushed in the stack
→ '/' comes. So, 60/6 = 10
→ '*' comes. So, 15 * 10 = 150
→ '8' comes, push in the stack
→ '' comes. So, 1508 = 142
So the final result is 142.
Question 41 
199  
198  
197  
196 
Question 42 
θ(n)  
θ(n+m)  
θ(n^{2} )  
θ(m^{2} ) 
Question 43 
1  
2  
3  
4 
Substitute into a and b values in equation.
⇒ a+10b
⇒ a*1 + 10*0
⇒ 1+0
⇒ 1
Question 44 
The graph does not have any topological ordering.  
Both PQRS and SRQP are topological.  
Both PSRQ and SPRQ are topological orderings.  
PSRQ is the only topological ordering. 
There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.
Question 45 
t_{1}=5  
t_{1}  
t_{1}>t_{2}  
t_{1}=t_{2} 
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2^{nd} array through not in sorted manner.
Hence t_{1}> t_{2}.
Question 46 
3, 0, and 1  
3, 3, and 3  
4, 0, and 1  
3, 0, and 2 
h(k) = k mod 9
Collisions are resolved using chaining.
Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.
5%9 – 5
28%9 – 1
19%9 – 1
15%9 – 6
20%9 – 2
33%9 – 6
12%9 – 3
17%9 – 8
10%9 – 1
Maximum chain length is 3
Minimum chain length is 0
Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1
Question 47 
int
MyX(
int
*E, unsigned
int
size)
{
int
Y = 0;
int
Z;
int
i, j, k;
for
(i = 0; i < size; i++)
Y = Y + E[i];
for
(i = 0; i < size; i++)
for
(j = i; j < size; j++)
{
Z = 0;
for
(k = i; k <= j; k++)
Z = Z + E[k];
if
(Z > Y)
Y = Z;
}
return
Y;
}
maximum possible sum of elements in any subarray of array E.  
maximum element in any subarray of array E.  
sum of the maximum elements in all possible subarrays of array E.  
the sum of all the elements in the array E. 
for (i=0; i
for (i=0; i
Z=0;
for(k=i; k<=j; k++)
Z=Z+E[k];
// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].
Store the current sum in Z.
If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.
Question 48 
D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3
Half of the product of the 3 consecutive integers.  
Onethird of the product of the 3 consecutive integers.  
Onesixth of the product of the 3 consecutive integers.  
None of the above. 
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3;
Also you can try for smaller ‘n’.
Question 49 
4  
5  
6  
7 
There were 2 stall cycles for pipelining for 25% of the instructions.
So pipeline time =(1+(25/100)*2)=3/2=1.5
Speed up =Nonpipeline time / Pipeline time=6/1.5=4
Question 50 
n⁄N  
1⁄N  
1⁄A  
k⁄n 
As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.
Question 51 
10, 8, 7, 3, 2, 1, 5  
10, 8, 7, 2, 3, 1, 5  
10, 8, 7, 1, 2, 3, 5  
10, 8, 7, 5, 3, 2, 1 
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 52 
the shortest path between every pair of vertices.  
the shortest path from W to every vertex in the graph.  
the shortest paths from W to only those nodes that are leaves of T.  
the longest path in the graph. 
But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.
Question 53 
Θ (n log n)  
Θ (n2^{n})  
Θ (n)  
Θ (log n) 
→ No of elements = n.2^{n} then search time = (log n.2^{n})
= (log n + log 2^{n})
= (log n + n log 2)
= O(n)
Question 54 
T(n) = 2T(n  2) + 2  
T(n) = 2T(n  1) + n  
T(n) = 2T(n/2) + 1  
T(n) = 2T(n  1) + 1 
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2^{2} T(n – 2) + 3
⋮
= 2^{k} T( n – k) + (2^{k} – 1)
n – k = 1
= 2^{n1} T(1) + (2^{n1} – 1)
= 2^{n1} + 2^{n1} – 1
= 2^{n} – 1
≌ O(2^{n})
Question 55 
full: (REAR+1)mod n == FRONT empty: REAR == FRONT  
full: (REAR+1)mod n == FRONT empty: (FRONT+1) mod n == REAR  
full: REAR == FRONT empty: (REAR+1) mod n == FRONT  
full: (FRONT+1)mod n == REAR empty: REAR == FRONT 
To circulate within the queue we have to write mod n for (Rear + 1).
We insert elements using Rear & delete through Front.
Question 56 
B1: (1+height(n→right)) B2: (1+max(h1,h2))  
B1: (height(n→right)) B2: (1+max(h1,h2))  
B1: height(n→right) B2: max(h1,h2)  
B1: (1+ height(n→right)) B2: max(h1,h2) 
Now, we analyze the code,
The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.
In such case, height of n will be the height of the right subtree +1.
The box B2 gets executed when both left & right subtrees of n are not NULL.
In such case, height of n will be max of heights of left & right subtrees of n+1.
Question 57 
Option A: It violates the property of complete binary tree.
Option C: 8 is greater than 5. The root value is always greater than his children. So, the above tree is violating the property of max heap
Option D: 10 is greater than 8. The root value is always greater than his children. So, the above tree is violating the property of max heap
Question 58 
0  
1  
n!  
Question 59 
0  
1  
(n1)/2  
n1 
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant.
― This is even number of descendants (2), because A is also considered as a descendant.
― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.
Question 60 
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; } 
q = NULL; p→next = head; head = p;
 
q→next = NULL; head = p; p→next = head;  
head = p; p→next = q; q→next = NULL;  
q→next = NULL; p→next = head; head = p;

The function modifies the list by moving the last element to the front of the list.
Let the list be 1 → 2 → 3 → 4 & the modified list must be 4 → 1 → 2 → 3.
Algorithm:
Traverse the list till last node. Use two pointers. One to store the address of last node & other for the address of second last node.
After completion of loop. Do these.
(i) Make second last as last
(ii) Set next of last as head
(iii) Make last as head
while (p → !=NULL)
{
q = p;
p = p → next;
}
― p is travelling till the end of list and assigning q to whatever p had visited & p takes next new node, so travels through the entire list.
Now the list looks like
According to the Algorithm new lines must be
q → next = NULL; p → next = head; head = p
Question 61 
7  
8  
9  
10 
Question 62 
46, 42, 34, 52, 23, 33
 
34, 42, 23, 52, 33, 46
 
46, 34, 42, 23, 52, 33  
42, 46, 33, 23, 34, 52

After inserting 6 values, the table looks like
The possible order in which the keys are inserted are:
34, 42, 23, 46 are at their respective slots 4, 2, 3, 6.
52, 33 are at different positions.
― 52 has come after 42, 23, 34 because, it has the collision with 42, because of linear probing, it should have occupy the next empty slot. So 52 is after 42, 23, 34.
― 33 is after 46, because it has the clash with 23. So it got placed in next empty slot 7, which means 2, 3, 4, 5, 6 are filled.
42, 23, 34 may occur in any order but before 52 & 46 may come anywhere but before 33.
So option (C)
Question 63 
10  
20  
30  
40 
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉can be sequenced in 3! ways.
Hence, 5×3! = 30 ways
Question 64 
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.
12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
Question 65 
2  
3  
4  
5 
2^{h}1=7
∴ h=3
Question 66 
{25,12,16,13,10,8,14}  
{25,14,13,16,10,8,12}  
{25,14,16,13,10,8,12}  
{25,14,12,13,10,8,16} 
Violating a max heap property.
OptionB:
Violating a max heap property.
OptionC:
Question 67 
{14,13,12,10,8}  
{14,12,13,8,10}  
{14,13,8,12,10}  
{14,13,12,8,10}

Step 1: Delete 25
Step 2:
Step 3: Delete 16
Step 4:
Step 5:
∴ Finary array elements: 14, 13, 12, 8, 10.
Question 68 
θ(n)  
θ(m)  
θ(m+n)  
θ(mn) 
Suppose if we are using Adjacency matrix means it takes θ(n^{2}).
Question 69 
Σm(4,6)  
Σm(4,8)  
Σm(6,8)  
Σm(4,6,8)

f_{1}*f_{2} is intersection of minterms of f_{1} and f_{2}
f= (f_{1}*f_{2}) + f_{3} is union of minterms of (f_{1}*f_{2}) and f_{3}
Σm(1,6,8,15)= Σm(4,5,6,7,8) * f_{2} + Σm(1,6,15)
Options A, B and D have minterm m_{4} which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f_{2}= Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
=Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f= LHS
Question 70 
MNOPQR
 
NQMPOR
 
QMNPRO
 
QMNPOR 
Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).
Question 71 
For every subset of k vertices, the induced subgraph has at most 2k–2 edges  
The minimum cut in G has at least two edges
 
There are two edgedisjoint paths between every pair to vertices
 
There are two vertexdisjoint paths between every pair of vertices 
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
> Option C: True: A spanning tree covers all the vertices. So, 2 edgedisjoint spanning trees in G means, between every pair of vertices in G we have two edgedisjoint paths (length of paths may vary).
Question 72 
θ(log n)
 
θ(n)  
θ(nlog n)
 
None of the above, as the tree cannot be uniquely determined

T(n) = T(k) + T(nk1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the inorder traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(nk1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 73 
θ(log n)  
θ(n)  
θ(nlog n)
 
θ(n^{2})

Note: We can also insert all the elements once, there will be no difference on time complexity.
Question 74 
1,2,3,4,5,6,7  
2,1,4,3,6,5,7  
1,3,2,5,4,7,6  
2,3,4,5,6,7,1

After 1st Iteration: 2,1,3,4,5,6,7
2nd Iteration: 2,1,4,3,5,6,7
3rd Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;
Hence 2,1,4,3,6,5,7.
Question 75 
The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)  
The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)  
The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)  
The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n) 
Question 76 
I and II are preorder and inorder sequences, respectively  
I and III are preorder and postorder sequences, respectively  
II is the inorder sequence, but nothing more can be said about the other two sequences  
II and III are the preorder and inorder sequences, respectively

So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.
Question 77 
I and III only  
II and III only  
II, III and IV only  
I, II and III only

IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.
Question 78 
2  
4  
6  
7 
Hence, correct option is (D).
Question 79 
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?
II and III only  
I and III only  
III and IV only  
III only 
Question 80 
I, II and IV are inorder sequences of three different BSTs  
I is a preorder sequence of some BST with 439 as the root  
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf  
IV is a postorder sequence of some BST with 149 as the root

B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.
Question 82 
n_{1} = 3
n_{2} = 1
n_{3} = 1
So, option (B) satisfies.
Question 83 
2 * n_{1} – 3  
n_{2} + 2 * n_{1} – 2  
n_{3} – n_{2}  
n_{2} + n_{1} – 2 
n_{1} = 3
n_{3} = 1
So, option (A) satisfies.
Question 84 
1 2 3 4 5 6  
1 3 2 4 5 6  
1 3 2 4 6 5  
3 2 4 1 6 5

(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.
Question 85 
2^{h}−1  
2^{h−1} – 1  
2^{h+1}– 1  
2^{h+1}

1,3,7,15,31,...=2^{h+1}  1
Question 86 
1  
5  
4  
3 
Total no. of possible trees is 5.
Total = 5
Question 87 
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:
6, 1
 
5, 7
 
3, 2  
1, 5 
After the * is evaluated at the time elements in the stack is 1, 6.
Question 88 
d e b f g c a
 
e d b g f c a  
e d b f g c a
 
d e f g b c a

Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g
Pre order: a b d e c f g
Post order: d e b f g c a
Question 89 
8, _, _, _, _, _, 10  
1, 8, 10, _, _, _, 3  
1, _, _, _, _, _,3
 
1, 10, 8, _, _, _, 3 
Starting index is zero i.e.,
⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).
Question 90 
A complete nary 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 nary tree. If L = 41, and I = 10, what is the value of n?
3  
4  
5  
6 
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n1) * 10 + 1
40 = (n1) * 10
n = 5
Question 91 
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 number of nodes in the tree
 
the number of internal nodes in the tree
 
the number of leaf nodes in the tree
 
the height of the tree

So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.
Question 92 
θ(log_{2}n)  
θ(log_{2}log_{2}n)  
θ(n)  
θ(nlog_{2}n)

Question 93 
d[u] < d[v]  
d[u] < f[v]  
f[u] < f[v]  
f[u] > f[v] 
Option A:
d[u]
d[u]
f[u]
Question 94 
35  
64  
128  
5040 
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 95 
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 ?
Leaves the queue Q unchanged  
Reverses the order of the elements in the queue Q  
Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order  
Empties the queue Q 
Question 96 
#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 + * +
15  
25  
30  
150 
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.
Question 97 
log_{2}n  
n  
2n+1
 
2^{n}1

Note: Assume level numbers are start with 0.
Question 98 
O(n)  
O(log n)  
O(log log n)
 
O(1) 
Question 99 
10, 7, 9, 8, 3, 1, 5, 2, 6, 4  
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
 
10, 9, 4, 5, 7, 6, 8, 2, 1, 3
 
10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Question 100 
1, 3, 5, 6, 8, 9
 
9, 6, 3, 1, 8, 5
 
9, 3, 6, 8, 5, 1
 
9, 5, 6, 8, 3, 1

Question 101 
There must exist a vertex w adjacent to both u and v in G
 
There must exist a vertex w whose removal disconnects u and v in G  
There must exist a cycle in G containing u and v
 
There must exist a cycle in G containing u and all its neighbours in G 
Question 102 
void insert(Q, x) { push (S1, x); } void delete (Q){ if (stackempty(S2)) then if (stackempty(S1)) then { print(“Q is empty”); return ; } else while (!(stackempty(S1))){ x=pop(S1); push(S2,x); } x=pop(S2); } 
n+m ≤ x < 2n and 2m ≤ y ≤ n+m
 
n+m ≤ x< 2n and 2m ≤y ≤ 2n  
2m ≤ x< 2n and 2m ≤ y ≤ n+m
 
2m ≤ x < 2n and 2m ≤ y ≤ 2n 
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (nm) elements to S1.
So total push operation
= m + m + (nm)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (nm) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
Question 103 
10  
11  
12  
15 
No. of 1 degree nodes = 5
No. of 2 degree nodes = 10
Total no. of edges = (1*5) + (2*10) = 5 + 20 = 25
So, Total no. of edges = 25 + 1 = 26 (No. of nodes in a tree is 1 more than no. of edges)
Total no. of leaf nodes (node with 0 degree) = 26  5  10 = 11
Question 104 
Hamiltonian cycle  
grid  
hypercube  
tree 
If all edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is minimum spanning tree.
Question 105 
{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}  
{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}  
{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}  
{23, 17, 14, 7, 13, 10, 1, 12, 5, 7} 
In this every children and parent satisfies Max heap properties.
Question 106 
Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?
{10, 75, 64, 43, 60, 57, 55}  
{90, 12, 68, 34, 62, 45, 55}  
{9, 85, 47, 68, 43, 57, 55}  
{79, 14, 72, 56, 16, 53, 55} 
Question 107 
{P, Q, R, S}, {T}, {U}, {V}  
{P, Q, R, S, T, V}, {U}  
{P, Q, S, T, V}, {R}, {U}  
{P, Q, R, S, T, U, V} 
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.
Question 108 
There is only one connected component  
There are two connected components, and P and R are connected  
There are two connected components, and Q and R are connected  
There are two connected components, and P and Q are connected 
Question 109 
⌊i/2⌋  
⌈(i1)/2⌉  
⌈i/2⌉  
⌈i/2⌉  1 
Question 110 
O(n)  
O(log n)  
O(n log n)  
O(n log log n) 
Question 111 
⌊log_{2} i⌋  
⌈log_{2} (i + 1)⌉  
⌊log_{2} (i + 1)⌋  
⌈log_{2} i⌉ 
Question 112 
Same as an abstract class
 
A data type that cannot be instantiated
 
A data type type for which only the operations defined on it can be used, but none else
 
All of the above 
Question 113 
An array of 50 numbers
 
An array of 100 numbers
 
An array of 500 numbers  
A dynamically allocated array of 550 numbers

→ Then using array of 50 numbers is the best way to store the frequencies.
Question 114 
Graph G has no minimum spanning tree (MST)
 
Graph G has a unique MST of cost n1
 
Graph G has multiple distinct MSTs, each of cost n1
 
Graph G has multiple spanning trees of different costs

Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n1).
Question 115 
the minimum weighted spanning tree of G
 
the weighted shortest path from s to t
 
each path from s to t
 
the weighted longest path from s to t

Question 116 
a path from s to t in the minimum weighted spanning tree
 
a weighted shortest path from s to t
 
an Euler walk from s to t
 
a Hamiltonian path from s to t

Minimum congestion is the edge with maximum weight among all other edges included in the path.
Now suppose shortest path from A→B is 6, but in MST, we have A→C→B(A→C=4, C→B=3), then along the path in MST, we have minimum congestion i.e., 4.
Question 117 
nk  
(n  1) k + 1
 
n (k  1) + 1
 
n (k  1)

Leaves = total nodes  internal nodes
= nk+1n
= n(k1)+1
Question 118 
5  
14  
24  
42 
(or)
t(0)=1
t(1)=1
t(4) = t(0)t(3) + t(1)t(2) + t(2)t(1) + t(3)t(0)
= 5+2+2+5
= 14
(or)
^{8}C_{4} / 5 = 14
Question 119 
10, 8, 7, 5, 3, 2, 1
 
10, 8, 7, 2, 3, 1, 5
 
10, 8, 7, 1, 2, 3, 5
 
10, 8, 7, 3, 2, 1, 5

Insert → 1 into heap structure
Insert → 7 into heap structure
Here, violating Maxheap property. So perform heapify operation.
The final sequence is 10, 8, 7, 3, 2, 1, 5.
Question 120 
9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
 
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
 
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
 
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29 
Question 121 
(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
 
top1 + top2 = MAXSIZE
 
(top1 = MAXSIZE/2) or (top2 = MAXSIZE)
 
top1 = top2 – 1

Question 122 
2  
3  
4  
6 
Height of the binary search tree = 3
Question 123 
queue
 
stack  
tree
 
list 
While evaluating when left parentheses occur then it push in to the stack, when right parentheses occur pop from the stack.
While at the end there is empty in the stack.
Question 124 
preorder traversal  
inorder traversal
 
depth first search
 
breadth first search

It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 125 
i only
 
ii only
 
i and ii only
 
iii or iv

Hash function = x mod 10
Hash values = (2, 4, 1, 9, 9, 1, 3, 9)
9679, 1989, 4199 have same hash values
&
1471, 6171 have same hash values.
Question 126 
(i) only  
(ii), (iii)
 
(iii) only
 
(iv) only

(i) Inorder and Preorder
(ii) Inorder and Postorder
(iii) Inorder and Levelorder
→And following are do not
(i) Post order and Preorder
(ii) Pre order and Level order
(iii) Post order and Level order
Question 127 
rear node
 
front node
 
not possible with a single pointer
 
node next to front

Question 128 
Question 129 
abc×+def^^
 
abc×+de^f^
 
ab+c×de^f^
 
+a×bc^^def

Note: When low precedence operator enters into stack then pop.
Question 130 
union only
 
intersection, membership
 
membership, cardinality
 
union, intersection

Let no. of elements in list 2 be n_{2}.
Union:
To union two lists, for each element in one list we will search in other list, to avoid duplicates. So, time complexity will be O(n_{1}×n_{2}).
Intersection:
To take intersection of two lists, for each element in one list we will search in other list if it is present or not. So time complexity will be O(n_{1} × n_{2}).
Membership:
In this we search if particular element is present in the list or not. So time complexity will be O(n_{1} + n_{2}).
Cardinality:
In this we find the size of set or list. So to find size of list we have to traverse each list once. So time complexity will be O(n_{1}+n_{2}).
Hence, Union and Intersection will be slowest.
Question 131 
The number of leaf nodes in the tree
 
The number of nodes in the tree
 
The number of internal nodes in the tree
 
The height of the tree

→ So given that pointer to root of tree is passed to DoSomething ( ), it will return height of the tree. It is done when the height of single node is '0'.
Question 132 
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worstcase time complexity of the best known algorithm to delete the node x from the list?
O(n)  
O(log^{2} n)  
O(logn)  
O(1) 
Question 133 
int *A [10], B[10][10]; 
I, II, and IV only  
II, III, and IV only  
II and IV only
 
IV only 
ii) A[2][3] This results an integer, no error will come.
iii) B[1] is a base address of an array. This will not be changed it will result a compile time error.
iv) B[2][3] This also results an integer. No error will come.
Question 134 
n – k + 1  
n – k  
n – k – 1
 
n – k – 2

Question 135 
7 5 1 0 3 2 4 6 8 9  
0 2 4 3 1 6 5 9 8 7  
0 1 2 3 4 5 6 7 8 9
 
9 8 6 4 2 3 0 1 5 7

Inorder: 0 1 2 3 4 5 6 7 8 9
Question 136 
(I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b eWhich are depth first traversals of the above graph?
I, II and IV only  
I and IV only  
II, III and IV only  
I, III and IV only

II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)
Question 137 
Θ(n log n)
 
Θ(n)  
Θ(log n)
 
Θ(1)

1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^{th} smallest element in Θ(1) time.
Question 138 
o Delection of the smallest element o Insertion of an element if it is not already present in the setWhich of the following data structures can be used for this purpose?
A heap can be used but not a balanced binary search tree  
A balanced binary search tree can be used but not a heap  
Both balanced binary search tree and heap can be used  
Neither balanced binary search tree nor heap can be used 
Insertion of an element takes O(n).
→ In balanced primary tree deletion takes O(log n).
Insertion also takes O(log n).
Question 139 
n(X + Y)  
3Y + 2X
 
n(X + Y)  X
 
Y + 2X 
(After push into stack then immediately popped)
Life time of (n1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n2) element = (n1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n1)X + (2n1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n1)+Y(1+3+5+...+(2n1))
⇒ 2X(n(n1) /2) +Y((n/2)(1+2n1))
⇒ n(n(X+Y)X))
Avg. of n numbers = n(n(X+Y)X)/n = n(X+Y)X
Question 140 
None of the above 
Insert G at root level:
Question 141 
struct item { int data; struct item * next; }; int f( struct item *p) { return ((p == NULL)  (p>next == NULL)  ((P>data <= p>next>data) && f(p>next))); } 
the list is empty or has exactly one element  
the elements in the list are sorted in nondecreasing order of data value
 
the elements in the list are sorted in nonincreasing order of data value
 
not all elements in the list have the same data value

Question 142 
log n  
n/2  
(log_{2})^{n}  1  
n 
Question 143 
Do not differ  
Differ in the presence of loops  
Differ in all cases  
May differ in the presence of exception 
Question 144 
Question 145 
4040  
4050  
5040  
5050 
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050
Question 146 
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n1/3)
No. of nodes in right sub tree = 2(n1/3)
Height of the tree = log_{3/2} n
Question 147 
One stack is enough  
Two stacks are needed  
As many stacks as the height of the expression tree are needed  
A Turning machine is needed in the general case 
Question 148 
Theory Explanation is given below. 
Total 5 binary trees are possible with the preorder C, B, A.
Question 149 
Theory Explanation is given below. 
move disk from source to dest //Step2
move (disk1, aux, dest, source) //Step3
Recurrence: 2T(n  1) + 1
T(n) = 2T (n  1) + 1
= 2[2T(n  2) + 1] + 1
= 2^{2}T(n  2) + 3
⁞
2^{k} T(n  k) + (2^{k}  1)
= 2^{n1}T(1) + (2^{n1}  1)
= 2^{n1} + 2^{n1}  1
= 2^{n}  1
≅ O(2^{n})
void move (int n, char A, char B, char C) {
if (n>0)
move(n1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n1, B, A, C);
}
}
Question 150 
X – 1 Y – 2 Z – 3  
X – 3 Y – 1 Z – 2  
X – 3 Y – 2 Z – 1  
X – 2 Y – 3 Z – 1 
Queus is used in Queue.
Heap is used in heap.
Question 151 
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?
(1 2 (4 5 6 7))  
(1 (2 3 4) 5 6) 7)  
(1 (2 3 4) (5 6 7))  
(1 (2 3 NULL) (4 5)) 
(Proper Representation)
Question 152 
Rotates s left by k positions  
Leaves s unchanged  
Reverses all elements of s  
None of the above 
Question 153 
LASTIN = LASTPOST  
LASTIN = LASTPRE  
LASTPRE = LASTPOST  
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 154 
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?
{u, v} must be an edge in G, and u is a descendant of v in T  
{u, v} must be an edge in G, and v is a descendant of u in T  
If {u, v} is not an edge in G then u is a leaf in T  
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 nodev. There is no need of (u,v) be an edge.
Question 155 
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 156 
0  
1  
2  
3 
Total no. of articulation points = 3
Question 157 
A tree with a n nodes has (n – 1) edges  
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results  
A complete binary tree with n internal nodes has (n + 1) leaves  
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 158 
x(n1) + 1  
xn  1  
xn + 1  
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 159 
15i + j + 84  
15j + i + 84  
10i + j + 89  
10j + i + 89 
100 + 15 * (i1) + (j1)
= 100 + 15i  15 + j  1
= 15i + j + 84
Question 160 
stack  
heap  
display  
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 161 
Singly linked list  
Doubly linked list  
Circular doubly linked list  
Array implementation of list 
Question 162 
An operator stack  
An operand stack  
An operand stack and an operator stack  
A parse tree

An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
Question 163 
5 3 1 2 4 7 8 6  
5 3 1 2 6 4 8 7  
5 3 2 4 1 6 7 8  
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 164 
nonincreasing order  
nondecreasing order  
strictly increasing order  
strictly decreasing order 
Question 165 
(ii) and (iii) are true  
(i) and (ii) are true  
(iii) and (iv) are true  
(ii) and (iv) are true 
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer: A
Question 166 
Worst case complexity of search operations is less?  
Space used is less  
Deletion is easier  
None of the above 
Question 167 
1  
3  
7  
8 
a, b, c are going to unbalance.
Question 168 
f e g c d b a  
g c b d a f e  
g c d b f e a  
f e d g c b a 
Left → Right → Root
g c d b f e a
Question 169 
0  
1  
2  
3 
Question 170 
(4, 7)  
(7, 4)  
(8, 3)  
(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 171 
log_{2} n  
n  1  
n  
2^{n} 
The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
The number of nodes of degree 2 in T is "n  1".
Question 172 
it makes it more difficult to verify programs  
it increases the running time of the programs  
it increases the memory required for the programs
 
it results in the compiler generating longer machine code 
Question 173 
3, 4, 5, 1, 2  
3, 4, 5, 2, 1  
1, 5, 2, 3, 4  
5, 4, 3, 1, 2 
→ Remaining options are not possible.
Question 174 
Insertion sort  
Binary search  
Radix sort  
Polynomial manipulation

Question 175 
4  
5  
6  
7  
Both A and D 
Where L is leaf node.
So, no. of internal node is 4.
Case 2:
Where L is leaf node.
So, no. of internal node is 7.
Question 176 
np 
Now, '0' edges for p1 vertices (p1 components) and np edges for np+1 vertices (1 component).
So, total of np edges for p components.
Question 177 
Left Child is at index: 2i
Right child is at index: 2*i+1
Question 178 
Only P3  
Only P1 and P3  
Only P1 and P2  
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 179 
d(r,u)  
d(r,u)>d(r,v)  
d(r,u)≤d(r,v)  
None of the above 
Question 180 
One  
Two  
Three  
Four 
Question 182 
(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 183 
Equal to the number of ways of multiplying (n+1) matrices.  
Equal to the number of ways of arranging n out of 2n distinct elements.
 
Equal to n!.
 
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 184 
≤ n^{2} always.  
≥ nlog_{2} n always.  
Equal to n^{2} always.  
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 × logn
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 185 
4  
5  
6  
3 
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisions = 4 + 1 = 5
Question 186 
(A)(r), (B)(s), (C)(p), (D)(q) 
O(n)  Selection of the k^{th} smallest element in a set of n elements
O(n log n)  Heapsort
O(n^{2})  Depthfirst search
Question 187 
Overlaying is used to run a program, which is longer than the address space of the computer.  
Optimal binary search tree construction can be performed efficiently by using dynamic programming.  
Depth first search cannot be used to find connected components of a graph.  
Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.  
A, C and D. 
As per the definition of address space memory used by the overlay comes under the address space of computer.
Option B: True
By using dynamic programming we can construct optimal binary search tree efficiently.
Option C: False
DFS can be used to find connected components of a graph.
Option D: False
Infix + C postfix or prefix is required to construct the binary tree uniquely.
Question 188 
True  
False 
Question 189 
True  
False 
Question 190 
True  
False 
In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.
Question 191 
One pointer.  
Two pointers.  
Multiple pointers.  
No pointer. 
p → next = q → next
q → next = p
So, two pointers modifications.