Data-Structures
Question 1 |
Consider the following statements:
- I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in Θ(n) time.
IV. A binary search tree can be constructed from a max-heap in Θ(n) time.
Which of the above statements are TRUE?
I, II and III | |
II, III and IV | |
I, III and IV | |
I, II and IV |
(ii) TRUE: The second smallest element in a heap is always a child of root node.

(iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.
Question 2 |
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 3 |
The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.
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 4 |
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?
θ(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 2nd last node which can be obtained by traversing the list which takes O(n) time.
Question 5 |
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
-
(I) No edge of G is a cross edge with respect to TD.
(A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, 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 6 |
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.
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 7 |
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
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 8 |
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.
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 9 |
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 10 |
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 11 |
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:
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 post-order traversal.
Question 12 |
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 | |
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 13 |
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 14 |
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 15 |
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?
O(1) | |
O(d) but not O(1) | |
O(2d) but not O(d) | |
O(d 2d) but not O(2d) |
→ 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 16 |
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry Wij 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 (C-B-A-D).
Question 17 |
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 18 |
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 n-th 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 ⇒ 25 - 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 19 |
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?
O(log2 N) | |
O(N) | |
O(N2) | |
Θ(N2 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(N2)
So, overall time complexity is, O(N2).
Question 20 |
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 _________.
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

∴ 20 + 21 + 22 + ⋯ + 2k = 1024
Add if 1(2(k+1)-1)/(2-1) [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 21 |
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:
+ - 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 22 |
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,
1st level - 2 (maximum or minimum)
⇓
2nd level - 2
⇓
3rd level - 2
⇓
4th level - 2
⇓
5th level - 2
⇓
6th level - 2
⇓
7th level - 2
= 2 × 2 × 2 × 2 × 2 × 2 × 1
= 26
= 64
Question 23 |
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 efficient algorithm to set the twin pointer in each entry in each adjacency list?
Θ(n2) | |
Θ(n+m) | |
Θ(m2) | |
Θ(n4) |
Visit every vertex level-wise 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 24 |
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
63 and 6, respectively | |
64 and 5, respectively | |
32 and 6, respectively | |
31 and 5, respectively |
2h+1 - 1 = 25+1 - 1 = 63
Minimum number of nodes in a binary tree of height h is
h + 1 = 5 + 1 = 6
Question 25 |
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
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 max-heap is (BFS)
40, 35, 20, 10, 30, 16, 17, 8, 4, 15
Question 26 |
A binary tree T has 20 leaves. The number of nodes in T having two children is _________.
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 - p - 1' (i.e., interval) vertices of degree 3
(iv) n - 1 edges
∴ By Handshaking theorem,
p × 1 + 1 × 2 + (n - p - 1) × 3 = 2(n - 1)
⇒n = 2p - 1
= 39 as p = 20
∴ n - p = 19 vertices have exactly two children
Question 27 |
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
Ω(logn) | |
Ω(n) | |
Ω(nlog n) | |
Ω(n2) |
Question 28 |
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?
h(i) = i2 mod 10 | |
h(i) = i3 mod 10 | |
h(i) = (11 *i2) mod 10 | |
h(i) = (12 * i) mod 10 |
Question 29 |
Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let α be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size the window scale option. Then the values of α and β are
63 milliseconds, 65535×214 | |
63 milliseconds, 65535×216 | |
500 milliseconds, 65535×214 | |
500 milliseconds, 65535×216 |
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 × 214.
Question 30 |
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.
1 2 5 14 3 4 6 23 10 12 18 25 31 ∞ ∞ ∞
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 in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is ____________.
4 | |
5 | |
6 | |
7 |

Question 31 |
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.
80 | |
70 | |
60 | |
50 |
Question 32 |
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
4 | |
5 | |
2 | |
3 |

→ Swap 100 & 15

→ Swap 100 & 50

→ Swap 89 & 100

∴ Total 3 interchanges are needed.
Question 33 |
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
65 | |
67 | |
69 | |
83 |

Question 34 |
The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is
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, 150-8 = 142

So the final result is 142.
Question 35 |
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____.
199 | |
198 | |
197 | |
196 |
Question 36 |
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
θ(n) | |
θ(n+m) | |
θ(n2) | |
θ(m2) |
Question 37 |
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(nalogbn). Then the value of a+10b is ________.
1 | |
2 | |
3 | |
4 |
Substitute into a and b values in equation.
⇒ a+10b
⇒ a*1 + 10*0
⇒ 1+0
⇒ 1
Question 38 |
Consider the directed graph given below.

Which one of the following is TRUE?
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 39 |
Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
t1=5 | |
t1 | |
t1>t2 | |
t1=t2 |
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 2nd array through not in sorted manner.
Hence t1> t2.
Question 40 |
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
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 41 |
Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the
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 sub-array of array E. | |
maximum element in any sub-array of array E. | |
sum of the maximum elements in all possible sub-arrays 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 42 |
Consider the following pseudo code. What is the total number of multiplications to be performed?
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. | |
One-third of the product of the 3 consecutive integers. | |
One-sixth 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 43 |
Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is _________.
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 =Non-pipeline time / Pipeline time=6/1.5=4
Question 44 |
An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?
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 45 |
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:
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 46 |
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
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 47 |
The worst case running time to search for an element in a balanced binary search tree with n2n elements is
Θ (n log n) | |
Θ (n2n) | |
Θ (n) | |
Θ (log n) |
→ No of elements = n.2n then search time = (log n.2n)
= (log n + log 2n)
= (log n + n log 2)
= O(n)
Question 48 |
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
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
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
Question 49 |
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
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 50 |
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.

The appropriate expression for the two boxes B1 and B2 are
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 51 |
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
![]() | |
![]() | |
![]() | |
![]() |
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 52 |
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?
0 | |
1 | |
n! | |
![]() |
Question 53 |
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?
0 | |
1 | |
(n-1)/2 | |
n-1 |
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 54 |
The following C function takes a simply-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.
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; }
Choose the correct alternative to replace the blank line.
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 55 |
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
7 | |
8 | |
9 | |
10 |

The minimum possible weight of a path p from vertex 1 to vertex 2 such that p contains atmost 3 edges,

= 1 + 4 + 3
= 8
Question 56 |
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?
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 57 |
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?
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 58 |
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?
![]() | |
![]() | |
![]() | |
![]() |
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 59 |
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.
2 | |
3 | |
4 | |
5 |
2h-1 = 7
∴ h=3

Question 60 |
Consider a binary max-heap implemented using an array.
Which one of the following array represents a binary max-heap?
{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.
Option-B:

Violating a max heap property.
Option-C:

Question 61 |
Consider a binary max-heap implemented using an array.
What is the content of the array after two delete operations on the correct answer to the previous question?
{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:

∴ Binary array elements: 14, 13, 12, 8, 10.
Question 62 |
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
θ(n) | |
θ(m) | |
θ(m+n) | |
θ(mn) |
Suppose if we are using Adjacency matrix means it takes θ(n2).
Question 63 |
Given f1, f3 and f in canonical sum of products form (in decimal) for the circuit
- f1 = Σm(4,5,6,7,8)
f3 = Σm(1,6,15)
f = Σm(1,6,8,15)
then f2 is
Σm(4,6) | |
Σm(4,8) | |
Σm(6,8) | |
Σm(4,6,8) |
f1*f2 is intersection of minterms of f1 and f2
f = (f1*f2) + f3 is union of minterms of (f1*f2) and f3
Σm(1,6,8,15) = Σm(4,5,6,7,8) * f2 + Σm(1,6,15)
Options A, B and D have minterm m4 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 f2 = Σ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 64 |
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

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 65 |
G is a graph on n vertices and 2n–2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
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 edge-disjoint paths between every pair to vertices | |
There are two vertex-disjoint 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 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).
Question 66 |
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?
θ(log n) | |
θ(n) | |
θ(nlog n) | |
None of the above, as the tree cannot be uniquely determined |
T(n) = T(k) + T(n-k-1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the in-order 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(n-k-1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 67 |
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
θ(log n) | |
θ(n) | |
θ(nlog n) | |
θ(n2) |
Note: We can also insert all the elements once, there will be no difference on time complexity.
Question 68 |
The following C function takes a single-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; } }
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;
‘p’ pointing to Null & q pointing to 7.
Hence 2,1,4,3,6,5,7.
Question 69 |
Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

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 70 |
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:
2h−1 | |
2h−1 – 1 | |
2h+1– 1 | |
2h+1
|
1, 3, 7, 15, 31, ... = 2h+1 - 1
Question 71 |
The maximum number of binary trees that can be formed with three unlabeled nodes is:
1 | |
5 | |
4 | |
3 |
Total no. of possible trees is 5.

Total = 5
Question 72 |
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:
6, 1 | |
5, 7 | |
3, 2 | |
1, 5 |

After the * is evaluated at the time elements in the stack is 1, 6.
Question 73 |
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
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 74 |
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
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 75 |
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?
3 | |
4 | |
5 | |
6 |
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n-1) * 10 + 1
40 = (n-1) * 10
n = 5
Question 76 |
Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) value = 1; else value = value + GetValue(ptr->leftChild) + GetValue(ptr->rightChild); } return(value); }The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:
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 77 |
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:
θ(log2n) | |
θ(log2log2n) | |
θ(n) | |
θ(nlog2n) |
Question 78 |
In a binary max heap containing n numbers, the smallest element can be found in time
O(n) | |
O(log n) | |
O(log log n) | |
O(1) |
We have to search all the elements to reach the smallest element and heap using linear search.
To traverse all elements using linear search will take O(n) time.
Question 79 |
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.
log2n | |
n | |
2n+1 | |
2n-1 |
Note: Assume level numbers are start with 0.
Question 80 |
Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?
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 81 |
An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) { push (S1, x); } void delete(Q){ if(stack-empty(S2)) then if(stack-empty(S1)) then { print(“Q is empty”); return; } else while (!(stack-empty(S1))){ x=pop(S1); push(S2,x); } x=pop(S2); }
Let n insert and m(<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
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 (n-m) elements to S1.
So total push operation
= m + m + (n-m)
= 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 (n-m) 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 82 |
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, is 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] location 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 3-ary max heap?
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 83 |
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, is 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] location 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 above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?
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 84 |
An Abstract Data Type (ADT) is:
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 85 |
A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
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 86 |
An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are l's. Which one of the following is TRUE?
Graph G has no minimum spanning tree (MST)
| |
Graph G has a unique MST of cost n-1 | |
Graph G has multiple distinct MSTs, each of cost n-1 | |
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., (n-1).
Question 87 |
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 inorder traversal of the tree T?
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 88 |
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
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 Max-heap property. So perform heapify operation.

The final sequence is 10, 8, 7, 3, 2, 1, 5.
Question 89 |
How many distinct binary search trees can be created out of 4 distinct keys?
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)
8C4 / 5 = 14
Question 90 |
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:
nk | |
(n - 1) k + 1 | |
n (k - 1) + 1 | |
n (k - 1) |
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1
Question 91 |
Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.
The edge e must definitely belong to:
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 92 |
Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.
Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?
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 93 |
A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is
(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
| |
top1 + top2 = MAXSIZE
| |
(top1 = MAXSIZE/2) or (top2 = MAXSIZE)
| |
top1 = top2 – 1 |
Question 94 |
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
2 | |
3 | |
4 | |
6 |

Height of the binary search tree = 3
Question 95 |
The best data structure to check whether an arithmetic expression has balanced parentheses is a
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 96 |
Level order traversal of a rooted tree can be done by starting from the root and performing
preorder traversal | |
in-order 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 97 |
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
-
i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 hash to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value
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 98 |
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?
(i) preorder and postorder (ii) inorder and postorder (iii) preorder and inorder (iv) level order and postorder
(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 99 |
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

rear node | |
front node | |
not possible with a single pointer | |
node next to front |
Question 100 |
The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is
![]() | |
![]() | |
![]() | |
![]() |







Question 101 |
abc×+def^^- | |
abc×+de^f^- | |
ab+c×d-e^f^ | |
-+a×bc^^def |

Note: When low precedence operator enters into stack then pop.
Question 102 |
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?
union only | |
intersection, membership
| |
membership, cardinality | |
union, intersection |
Let no. of elements in list 2 be n2.
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(n1×n2).
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(n1 × n2).
Membership:
In this we search if particular element is present in the list or not. So time complexity will be O(n1 + n2).
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(n1+n2).
Hence, Union and Intersection will be slowest.
Question 103 |
Consider the following C program segment
struct CellNode { struct CelINode *leftchild; int element; struct CelINode *rightChild; } int Dosomething(struct CelINode *ptr) { int value = 0; if (ptr != NULL) { if (ptr->leftChild != NULL) value = 1 + DoSomething(ptr->leftChild); if (ptr->rightChild != NULL) value = max(value, 1 + DoSomething(ptr->rightChild)); } return (value); }
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is
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 104 |
Assume the following C variable declaration
int *A [10], B[10][10];
Of the following expressions
I. A[2] II. A[2][3] III. B[1] IV. B[2][3]
which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
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 105 |
Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is
n – k + 1 | |
n – k | |
n – k – 1 | |
n – k – 2 |

Question 106 |
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
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 107 |
Consider the following graph

Among the following sequences:
(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 e
Which 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 108 |
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
Θ(n log n) | |
Θ(n) | |
Θ(log n) | |
Θ(1) |
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7th smallest element in Θ(1) time.
Question 109 |
A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set.
- I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which 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 110 |
Let S be a stack of size n≥1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m≥1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is
n(X + Y) | |
3Y + 2X | |
n(X + Y) - X | |
Y + 2X |
(After push into stack then immediately popped)
Life time of (n-1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n-2) element = (n-1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n-1)X + (2n-1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n-1)+Y(1+3+5+...+(2n-1))
⇒ 2X(n(n-1) /2) +Y((n/2)(1+2n-1))
⇒ n(n(X+Y)-X))
Avg. of n numbers = n(n(X+Y)-X)/n = n(X+Y)-X
Question 111 |
Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting G in the above tree?
![]() | |
![]() | |
![]() | |
None of the above |

Insert G at root level:

Question 112 |
Consider the function f defined below.
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))); }
For a given linked list p, the function f returns 1 if and only if
the list is empty or has exactly one element | |
the elements in the list are sorted in non-decreasing order of data value
| |
the elements in the list are sorted in non-increasing order of data value
| |
not all elements in the list have the same data value |
Question 113 |
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
log n | |
n/2 | |
(log2)n - 1 | |
n |
Question 114 |
The results returned by function under value-result and reference parameter passing conventions
Do not differ | |
Differ in the presence of loops | |
Differ in all cases | |
May differ in the presence of exception |
Question 115 |
Consider the following declaration of a two dimensional array in C:
char a[100][100];
Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a [40][50] is:
4040 | |
4050 | |
5040 | |
5050 |
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050
Question 116 |
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
n/2 | |
(n-1)/3 | |
(n-1)/2 | |
(2n+1)/3 |

Question 117 |
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?
log2n | |
log4/3n | |
log3n | |
log3/2n |
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log3/2 n
Question 118 |
To evaluate an expression without any embedded function calls
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 119 |
Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.
Theory Explanation is given below. |

Total 5 binary trees are possible with the preorder C, B, A.
Question 120 |
The following recursive function in C is a solution to the Towers of Hanoi problem.
Void move (int n, char A, char B, char C) { if (…………………………………) { move (…………………………………); printf(“Move disk %d from pole %c to pole %c\n”, n,A,C); move (………………………………….);
Fill in the dotted parts of the solution.
Theory Explanation is given below. |
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3
⁞
2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
Question 121 |
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
i-1 | |
⌊i/2⌋ | |
⌈i/2⌉ | |
(i+1)/2 |
Left Child is at index: 2i
Right child is at index: 2*i+1
Question 122 |
Consider an undirected unweighted graph G. Let a breadth-first 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 breadth-first traversal, which of the following statements is correct?
d(r,u) | |
d(r,u)>d(r,v) | |
d(r,u)≤d(r,v) | |
None of the above |
Question 123 |
What is the minimum number of stacks of size n required to implement a queue of size n?
One | |
Two | |
Three | |
Four |
Question 124 |
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?
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 125 |
(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 _____________; }
Theory Explanation is given below. |
Question 126 |
The most appropriate matching for the following pairs
X: depth first search 1: heap Y: breadth-first search 2: queue Z: sorting 3: stack
is
X – 1 Y – 2 Z – 3 | |
X – 3 Y – 1 Z – 2 | |
X – 3 Y – 2 Z – 1 | |
X – 2 Y – 3 Z – 1 |
Queue is used in breadth-first search.
Heap is used in heap.
Question 127 |
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 128 |
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);
Rotates s left by k positions | |
Leaves s unchanged | |
Reverses all elements of s | |
None of the above |
Question 129 |
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?
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 130 |
Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first 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 node v. There is no need of (u,v) be an edge.
Question 131 |
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.
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 132 |
The number of articulation points of the following graph is

0 | |
1 | |
2 | |
3 |
Total no. of articulation points = 3
Question 133 |
Which of the following statements is false?
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 2h+1 - 1.
h=2 ⇒ 23 - 1 ⇒ 7

Question 134 |
A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by
x(n-1) + 1 | |
xn - 1 | |
xn + 1 | |
x(n+1) |
Let no. of leaf nodes = L
Let nt be total no. of nodes.
So, L+x = nt -----(I)
Also for n-ary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = nt -----(II)
So, equating (I) & (II),
L+x = nx+1
L = x(n-1) + 1
Question 135 |
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 row-major order and the first element of the array is stored at location 100, what is the address of the element a[i][j]?
15i + j + 84 | |
15j + i + 84 | |
10i + j + 89 | |
10j + i + 89 |
100 + 15 * (i-1) + (j-1)
= 100 + 15i - 15 + j - 1
= 15i + j + 84
Question 136 |
Faster access to non-local variables is achieved using an array of pointers to activation records called a
stack | |
heap | |
display | |
activation tree |
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for non-local variables but may be complicated to maintain.
Question 137 |
The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?
Singly linked list | |
Doubly linked list | |
Circular doubly linked list | |
Array implementation of list |
Question 138 |
Which of the following is essential for converting an infix expression to the postfix from efficiently?
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 139 |
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?
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 140 |
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
non-increasing order | |
non-decreasing order | |
strictly increasing order | |
strictly decreasing order |
Question 141 |
Consider the following statements:
- (i) First-in-first 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) Last-in-first-out type of computations are efficiently supported by QUEUES.
Which of the following is correct?
(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 142 |
An advantage of chained hash table (external hashing) over the open addressing scheme is
Worst case complexity of search operations is less? | |
Space used is less | |
Deletion is easier | |
None of the above |
Question 143 |
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”?

1 | |
3 | |
7 | |
8 |

a, b, c are going to unbalance.
Question 144 |
Which of the following sequences denotes the post order traversal sequence of the tree of question 14?
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 145 |
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
0 | |
1 | |
2 | |
3 |


Question 146 |
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
(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 147 |
An unrestricted use of the “goto” statement is harmful because
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 148 |
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?
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 149 |
Linked lists are not suitable data structures of which one of the following problems?
Insertion sort | |
Binary search | |
Radix sort | |
Polynomial manipulation
|
Question 150 |
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?
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 |


Postorder:
11, 12, 10, 16, 19, 18, 20, 15
Question 151 |
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 + (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 _______.
13 |
• K=90
• h1(k) = k mod 23 = 90 mod 23 = 21
• In case of collision, we need to use secondary hash function.
• h2(k) = 1 + (k mod19) = 1 + 90mod19 = 1+14 = 15
• Now (21+15) mod 23 = 36 mod 23 = 13
• So the address is 13.
Question 152 |
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?
θ(n log n) | |
θ(n2) | |
θ(1) | |
θ(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(n2) and heap sort will not be suitable to apply.
Question 153 |
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 _______.
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 154 |
What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
θ(n4)
| |
θ(n2)
| |
θ(n3) | |
θ(n2 log n) |
In question they asked about n2 elements.
So, In worst case it will take o(n2 log n) time.
Question 155 |
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, _______”.
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 | |
if and only if ∀u ∈ V, f(u) is positive
| |
if and only if ∀u ∈ V, f(u) is negative | |
for every f: V→R |


Question 156 |
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.
θ(n log k) | |
θ(log n + k) | |
θ(k log n) | |
θ(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 157 |
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
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
= 512-1
= 511
Question 158 |
A 2-3 tree is tree such that
- (a) all internal nodes have either 2 or 3 children
(b) all paths from root to the leaves have the same length
The number of internal nodes of a 2-3 tree having 9 leaves could be
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 159 |
How many edges are there in a forest with p components having n vertices in all?
n-p |
Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).
So, total of n-p edges for p components.
Question 160 |
Match the pairs in the following questions:
(a) A heap construction (p) Ω(n log10 n) (b) Constructing Hash table with linear probing (q) O(n) (c) AVL Tree construction (r) O(n2) (d) Digital trie construction (s) O(n log10 n)
(a) - (q), (b) - (r), (c) - (s), (d) - (p) |
Constructing Hash table with linear probing - O(n2
AVL tree construction - O(n log10 n)
Digital trie construction - Ω(n log10 n)
Question 161 |
Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,
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 nth catalan number.
Question 162 |
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 = ∑wIw, where Iw is the path length of external node w),≤ n2 always. | |
≥ n log2 n always. | |
Equal to n2 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 × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 163 |
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

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 comparisons = 4 + 1 = 5
Question 164 |
Match the pairs in the following questions:
(A) O(log n) (p) Heapsort (B) O(n) (q) Depth-first search (C) O(n log n) (r) Binary search (D) O(n2) (s) Selection of the kth smallest element in a set of n elements.
(A)-(r), (B)-(s), (C)-(p), (D)-(q) |
O(n) - Selection of the kth smallest element in a set of n elements
O(n log n) - Heapsort
O(n2) - Depth-first search
Question 165 |
Which one of the following statements(s) is/are FALSE?
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 166 |
It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?
True | |
False |
Question 167 |
There is a linear-time algorithm for testing the planarity of finite graphs.
True | |
False |
Question 168 |
If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.
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 169 |
In a circular linked list organisation, insertion of a record involves modification of
One pointer. | |
Two pointers. | |
Multiple pointers. | |
No pointer. |
p → next = q → next
q → next = p
So, two pointers modifications.
Question 170 |
Which of the following is TRUE?
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 171 |
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.
MBCAFHPYK KAMCBYPFH MABCKYFPHPick the true statement from the following.
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 172 |
Consider the following sequence of nodes for the undirected graph given below.
a b e f d g c a b e f c g d a d g e b c f a d b c g e fA Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

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 173 |
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys
43 36 92 87 11 4 71 13 14is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?
2 | |
4 | |
6 | |
7 |

Hence, correct option is (D).
Question 174 |
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 175 |
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
Which of the following statements is TRUE?
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 176 |
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
How many distinct BSTs can be constructed with 3 distinct keys?
4 | |
5 | |
6 | |
9 |
2nCn/n+1 = 6C3/7 = 5
Question 177 |
A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n3 can be expressed as
n1 + n2 - 1 | |
n1 - 2 | |
[((n1 + n2)/2)] | |
n2 - 1 |

n1 = 3
n2 = 1
n3 = 1
So, option (B) satisfies.
Question 178 |
A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?
2 * n1 – 3 | |
n2 + 2 * n1 – 2 | |
n3 – n2 | |
n2 + n1 – 2 |

n1 = 3
n3 = 1
So, option (A) satisfies.
Question 179 |
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph?
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 180 |
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
35 | |
64 | |
128 | |
5040 |
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 181 |
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
(i) isEmpty (Q) — returns true if the queue is empty, false otherwise.
(ii) delete (Q) — deletes the element at the front of the queue and returns its value.
(iii) insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
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 182 |
Consider the following C program:
#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 183 |
In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is
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 184 |
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a
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 185 |
Which of the following sequences of array elements forms a heap?
{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 186 |
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 187 |
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

{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 188 |
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units f(P) = 12 units d(Q) = 6 units f(Q) = 10 units d(R) = 14 unit f(R) = 18 units
Which one of the following statements is TRUE about the graph?
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 189 |
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?
⌊i/2⌋ | |
⌈(i-1)/2⌉ | |
⌈i/2⌉ | |
⌈i/2⌉ - 1 |
Question 190 |
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of
O(n) | |
O(log n) | |
O(n log n) | |
O(n log log n) |
Question 191 |
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is
⌊log2 i⌋ | |
⌈log2 (i + 1)⌉ | |
⌊log2 (i + 1)⌋ | |
⌈log2 i⌉ |
Question 192 |
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?
O(n) | |
O(log2 n) | |
O(logn) | |
O(1) |
Question 193 |
Finding the diameter of the graph | |
Finding the bipartite graph | |
Both (a) and (b) | |
None of the above |
Examples
1. Copying garbage collection, Cheney's algorithm
2. Find the diameter of the graph
3. Testing bipartiteness of a graph.
4. Finding the shortest path between two nodes u and v, with path length measured by the number of edges (an advantage over depth-first search)
5. (Reverse) Cuthill–McKee mesh numbering
6. Ford–Fulkerson method for computing the maximum flow in a flow network
7. Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be reconstructed in an efficient manner.
8. Construction of the failure function of the Aho-Corasick pattern matcher.
Question 194 |

X→ Bwd→ Fwd = X→ Fwd; X→ Fwd → Bwd = X→ Bwd ; | |
X→ Bwd.Fwd = X→ Fwd ; X.Fwd→ Bwd = X→ Bwd ; | |
X.Bwd→ Fwd = X.Bwd ; X→ Fwd.Bwd = X.Bwd ; | |
X→ Bwd→ Fwd = X→ Bwd ; X→ Fwd→ Bwd = X→ Fwd; |
we need x→ Bwd→ Fwd = x.
Fwd and in order to link z to y, we need x→ Fwd→ Bwd=x→ Bwd.
Question 195 |

Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence?
Preorder, Postorder | |
Postorder, Inorder | |
Postorder, Preorder | |
Inorder, Preorder |
→ Post order traverses Left, Right, Root.
→ In-order traverses Left, Root, Right.
Tree-1: Post order: GJIHEFBDCA
Tree-2: In order: GJIHEFBDCA
Question 196 |
A | |
B | |
C | |
D |
Question 197 |

Delete the last element of the list | |
Delete the first element of the list | |
Add an element after the last element of the list | |
Interchange the first two elements of the list |
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Question 198 |
all zeros | |
all ones | |
both zeros and ones | |
different |
Question 199 |
14,13,8,12,10 | |
14,12,13,10,8 | |
14,13,12,8,10 | |
14,13,12,10,8 |

Step-2: We have to perform 2 delete operations.
In max-heap (or) min-heap by default we are deleting root element only.
After 1st delete, the heap structure is

Step-3: After 2nd delete operation, the heap structure is

Question 200 |

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 number of comparisons = 4 + 1 = 5
Question 201 |
I. P has a local variable
II. P has an execution path where it does not call itself
III. P either refers to a global variable or has at least one parameter
I only | |
II only | |
III only | |
II and III only |
→ P has an execution path where it does not call itself
→ P either refers to a global variable or has at least one parameter
Recursion Rules
Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
The recursive calls must eventually reach a base case, which is solved without further recursion.
Question 202 |
Type COLOGNE : (LIME, PINE, MUSK, MENTHOL); var a : array [COLOGNE] of REAL; | |
var a : array [REAL] of REAL; | |
var a : array [‘A’…’Z’] of REAL; | |
var a : array [BOOLEAN] of REAL; |
Expect the option B, All remaining indexes are not real numbers.
Option A , takes enum value as index which is integer number.
Option C, takes character which is having equivalent decimal value.
Option D, has boolean value as index whose value may be 0 or 1
Question 203 |
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
Both are true | |
Both are false | |
First is false and second is true | |
None of the above |
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
Question 204 |
Stack | |
List | |
Queue | |
None of the above |

Question 205 |
15 | |
10 | |
7 | |
9 |
The number of distinct simple graphs with up to three nodes:

So, total 7 unlabeled nodes are possible. Option (C) is correct.
Question 206 |
n2 | |
n * (n-1)/2 | |
n – 1 | |
(n + 1) * n/2 |
Question 207 |
Queue | |
Stack | |
Tree | |
List |
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.
Question 208 |
A secondary access path | |
A physical record key | |
An inverted index | |
A primary key |
1. To understand how pointers and their associated data elements are allocated in Microsoft RPC, you have to differentiate between top-level pointers and embedded pointers
2. Top-level pointers are those that are specified as the names of parameters in function prototypes. Top-level pointers and their referents are always allocated on the server.
3. Embedded pointers are pointers that are embedded in data structures such as arrays, structures, and unions. When embedded pointers only write output to a buffer and are null on input, the server application can change their values to non-null. In this case, the client stubs allocate new memory for this data.
4. If the embedded pointer is not null on the client before the call, the stubs do not allocate memory on the client on return. Instead, the stubs attempt to write the memory associated with the embedded pointer into the existing memory on the client associated with that pointer, overwriting the data already there.
Question 209 |
* +a − bc /− de − +fgh | |
* +a −bc − /de − +fgh | |
* +a − bc /− ed + −fgh | |
* +ab − c /− ed + −fgh |


Question 210 |
4 | |
0 | |
1 | |
None of these |
Note: Excluded for evaluation.
Question 211 |
function F(K : integer)
integer;
begin
if (k<3) then F:=k
else F:=F(k-1)*F(k-2)+F(k-3)
end;
5 | |
6 | |
7 | |
8 |
F(4) = F(3)*F(2)+F(1) = 5
F(3) = F(2)*F(1)+F(0) = 2
F(2) = 2
F(1) = 1
F(0) = 0
Question 212 |
b a c | |
b c a | |
c a b | |
a b c |
Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c
Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a
Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
Question 213 |
O(log n) | |
O(n) | |
O(1) | |
(n2) |
Question 214 |
Deleting a node whose location is given | |
Searching an unsorted list for a given item | |
Inserting a node after the node with a given location | |
Traversing the list to process each node |
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.
The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Question 215 |
O(log n) | |
O(n) | |
O(1) | |
O(n2) |
Question 216 |
binary search tree | |
AVL tree | |
completely balanced tree | |
Heap |
Question 217 |
1 | |
2 | |
3 | |
4 |
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
Question 218 |
A+B−C∗D | |
+A∗−BCD | |
ABC−D∗+ | |
A+BC−D∗ |
Given Expression = A + (B – C)* D
Prefix Notation:
A + (- B C) * D
A + (* - B C D)
+ A * - B C D
Question 219 |
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 |
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.

Question 220 |
3 | |
4 | |
5 | |
6 |
Hash function = f(key) = key mod 7

Question 221 |
log2n nodes | |
n+1 nodes | |
2n nodes | |
2n+1 nodes |
Note: if two leaves having the same parent are removed from the tree, the number of leaves and non-leaves will decrease by 1 because the parent will be a leaf. That means the difference between them is constant. And for a tree having just one node that difference is 1.
Question 222 |
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 |
The in-order traversal of BST will gives the elements in the sorted order( ascending order)
Question 223 |
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which 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 search tree nor heap can be used |
A self-balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a self balancing BST, we can easily find out minimum element in O(logn) time which is always the leftmost element.
Question 224 |
2 | |
3 | |
4 | |
6 |

So, height of the tree is defined maximum distance of a leaf node from the root.The root node is “10” and lead node is “5”.The maximum distance is 3
Question 225 |
abc x + def ^ ^ − | |
abc x + de ^ f ^ − | |
ab + c × d − e^f^ | |
− + a × b c^^ def |
The operators in the expression are +,x,- ^
First we will convert e^f ad ef^ (as highest precedence and right associativity) and later
d ^( e f ^ ) to def^^ and so on , you can find the same thing from the below steps.
The postfix expression:
a + b × c − ( d ^( e ^ f))
a + b × c − ( d ^( e f ^ ))
a + b × c − ( d e f ^ ^)
(a + (b × c)) − d e f ^ ^
(a + (b c x)) − d e f ^ ^
(a (b c x) +) − d e f ^ ^
(a b c x +) - (d e f ^ ^)
(a b c x +) - (d e f ^ ^)
a b c x + d e f ^ ^ -
Question 226 |
1267 | |
1164 | |
1264 | |
1169 |
Base or starting address of the array is 1120.
The address of the 49th element = base address of array + number of elements before current element * size of element
= 1120 + 48 * 3 = 1264
Question 227 |
A | |
B | |
C | |
D |

Question 228 |
n nodes | |
log2 n nodes | |
2n-1 | |
2n |

Question 229 |
3230 | |
16230 | |
49152 | |
173458 |
Between * and ^ , operator ‘^’ is highest precedence so it will execute first.
The expression consists of more than one ‘^’ operator is presented then it will follow right to left associativity.
Multiplication operator associativity is left to right.
1 * 2 ^ 3 * 4 ^ 5 * 6 = 1 * (2 ^ 3)* (4 ^ 5) * 6
= 1 * 8 * 1024 * 6
= 49152
Question 230 |
5 | |
14 | |
24 | |
35 |
So, for 4 distinct nodes, we can have (8C4)/5 = 14 distinct BSTs
Question 231 |
0 | |
3 | |
4 | |
None of the above |
According to question, there is no information regarding children nodes of node “A”. So the degree of A is 0.
Question 232 |
x:=1;
i:=1;
while (x ≤ 500)
begin
x:=2x ;
i:=i+1;
end
What is the value of i at the end of the pseudocode?
4 | |
5 | |
6 | |
7 |
After completion of second iteration x and i values are : x = 4 and i = 3
After completion of third iteration x and i values are : x = 16 and i = 4
After completion of fourth iteration x and i values are : x =256 and i = 5
After completion of fifth iteration x and i values are : x = 65536 and i = 6(Condition is false)
Then the value of “i” is 5
Question 233 |
O(n0.5) | |
O(n) | |
O(log n) | |
O(n log n) |
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.
The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.
The average depth of a binary search tree is log(n)
Question 234 |
FGBDECA | |
ABFGCDE | |
BFGCDEA | |
AFGBDEC |
→ Pre order properties are root,left and right
→ Based on the given sequence, we will get binary tree is

→ Based upon the inorder traversal, we will get preorder sequence is ABFGCDE.
Question 235 |
0.164 | |
127 | |
8.06 | |
6.08 |
Symbol table length=152,
Number of entries=25,
Occupation density=?
Step-1: To find Occupation density require number of entries and length of symbol table.
Occupation Density = Number of entries/ Length of symbol table
= 25/152
= 0.164
Question 236 |
p = getnode()
info (p) = 10
next (p) = list
list = p
result in which type of operation?
pop operation in stack | |
removal of a node | |
inserting a node | |
modifying an existing node |
info (p) = 10 // Storing the value of 10 into the info field of new node
next (p) = list // adding new node to the existing list.
list=p // the starting address of the list will
point to the new node
Question 237 |
8 | |
15 | |
14 | |
13 |

Question 238 |
1 | |
2 | |
N/2 | |
2N-1 |
Array=2N elements
Elements are used 2-ordered and 3-ordered
Step-1: If array used 2-ordered, if it contains an element which is at most two positions away from its original position in a sorted array.
Sep-2: Maximum number of positions that an element can be from its position if the array were
1-ordered = 1
Question 239 |
2 | |
3 | |
4 | |
5 |
The “current” binding for a given name is the one encountered most recently during execution
Dynamic scoping :
The scope of bindings is determined at run time not at Compile time .
→ For deep binding, the referencing environment is bundled with the subroutine as a closure and passed as an argument. A subroutine closure contains
– A pointer to the subroutine code
– The current set of name-to-object bindings
→ By considering dynamic scoping with deep binding when add is passed into second the environment is x = 1, y = 3 and the x is the global x so it writes 4 into the global x, which is the one picked up by the write_integer.
Question 240 |
0 | |
1 | |
2 | |
3 |


Question 241 |
1200 | |
1408 | |
33 | |
1050 |
In the given question, Array is represented with lower bound and upper bound.
The following ARRAY statement defines an array containing a total of five elements, a lower bound of 72, and an upper bound of 76. It represents the calendar years 1972 through 1976: array years{72:76} first second third fourth fifth.
The following ARRAY statement arranges the variables in an array by decades. The rows range from 6 through 9, and the columns range from 0 through 9.
array X{6:9,0:9} X60-X99.

Question 242 |
q[0] | |
q[1] | |
q[9] | |
q[10] |
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer
Question 243 |

Q | |
V | |
W | |
X |
The in-order traversal of the above tree is UQXWPVZY
So the fourth smallest element is 4th element of the inorder which is W
Question 244 |
A | |
B | |
C | |
D |

Question 245 |
0 | |
1 | |
11 | |
12 |
661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11, already filled, so after linear probing it will get index 12
103 mod 13 = 12, already filled, so after linear probing it will get index 1
Question 246 |
30 | |
60 | |
90 | |
None of the above |
n=4. Here, n is number of nodes.
44-2=16.
Given options are wrong options.
Note: Correct answer is 16
Question 247 |
Values of local variables | |
Return address | |
Heap area | |
Information needed to access non local variables |
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time
Question 248 |

Delete the first element of the list | |
Interchange the first two elements of the list | |
Delete the last element of the list | |
Add an element at the end of the list |
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
Question 249 |
Consider the array A = 〈4, 1, 3, 2, 16, 9, 10, 14, 8, 7〉. After building heap from the array A, the depth of the heap and the right child of max-heap are and respectively. (Root is at level 0).
3, 14 | |
3, 10 | |
4, 14 | |
4, 10 |
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max-heapify operation from the largest index parent node (node having 1 or more children).






The above Heap is the max-heap where each root node have maximum value.
Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 250 |
A hash function h defined h(key) = key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?
3 | |
4 | |
5 | |
6 |
h(44) = 44 mod 7 ⇒ 2
h(45) = 45 mod 7 ⇒ 3
h(79) = 79 mod 7 ⇒ 2 (collision occurred)
h(79) = (79+1) mod 7 ⇒ 3 (collision occurred)
h(79) = (79+2) mod 7 ⇒ 4
h(55) = 55 mod 7 ⇒ 6
h(91) = 91 mod 7 ⇒ 0
h(18) = 18 mod 7 ⇒ 4 (collision occurred)
h(79) = (18+1) mod 7 ⇒ 5
h(63) = 63 mod 7 ⇒ 0 (collision occurred)
h(63) = (63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations.

Question 251 |
Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. 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 ?
Here “__” denotes an empty location in the table.
3, 10, 1, 8, ___ , ___, ___.
| |
1, 3, 8, 10, ___, ___, ___.
| |
1, ___, 3, ___, 8, ___, 10
| |
3, 10, ___, ___, 8, ___, ___. |
h(3) = ((7*3)+3) mod 4 = 0
h(8) = ((7*8)+3) mod 4 = 3
h(10) = ((7*10)+3) mod 4 = 1

Question 252 |
n/2 | |
(2n+1)/3 | |
(n-1)/n | |
(n-1) |
[ Where L is the number of leaf nodes and I is the number of internal nodes]
→ Given data n=3.
L=(3-1)I +1
=2I +1 ------------> 1
→ To find total number of nodes is nothing but sum of leaf nodes and internal nodes
n=L+I ------------> 2
With the help of 1 and 2, we get L =(2n+1)/3/
Question 253 |
Array | |
Tree | |
Stack | |
Queue |
→ Stack to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes.
→ The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls.
→ This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Question 254 |
10 10 +60 6 / * 8 - is:
192 | |
190 | |
110 | |
92 |


Question 255 |
Preorder and Inorder | |
Postorder and Inorder | |
Postorder and Preorder | |
None of these |
Consider two different trees,
TREE-1
root=a;
root→ left=b;
root→ left→ right=c;
TREE-2
root=a;
root→ right=b;
root→ right→ left=c;
Both the trees are different, but have same pre-order and post-order sequence.
pre-order - a b c
post-order - c b a
Because we cannot separate the left subtree and right subtree using the pre-order or post-order traversal alone
Question 256 |
Two stacks are required | |
One stack is needed | |
Three stacks are required | |
More than three stacks are required |
Converting infix expression into post/prefix expression
Evaluating post/pre-fix expression
Parenthesis matching
With one stack also we can easily evaluate the expression.
Question 257 |
1 | |
2 | |
3 | |
4 |
push(s,x)
1) Enqueue x to q1 (assuming size of q1 is unlimited). pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
Question 258 |
4 | |
8 | |
16 | |
32 |
Question 259 |
Circular queue | |
Priority queue | |
Stack | |
Dequeue |
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Question 260 |
Queue | |
Stack | |
List | |
None of above |
Question 261 |
Depth First | |
Breadth First | |
Width First | |
Depth Limited |
● Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 262 |
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
Prints all nodes of linked lists | |
Prints all nodes of linked list in reverse order | |
Prints alternate nodes of Linked List | |
Prints alternate nodes in reverse order |
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next
// Now change next of current
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 263 |
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <--> 2 <--> 3 <--> 4<--> 5 <--> 6. What should be the modified linked list after the function call?
1<-->2<-->4<-->3<-->6<-->5 | |
5<-->4<-->3<-->2<-->1<-->6 | |
6<-->5<-->4<-->3<-->2<-->1 | |
6<-->5<-->4<-->3<-->1<-->2 |
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 264 |
void fun(int n)
{
Stack s;//Say it creates an empty stack S
while(n>0)
{
// This line pushes the value of n%2 to
Stack S;
Push(&S,n%2);
n=n/2l
}
// Run while Stack S is not empty
while(!is Empty(&S)) Printf(%d",pop(&S));//pop an element from S and print it
}
What does the above function do in general order
Prints binary representation of n in reverse order | |
prints binary representation of n | |
Prints the value of Logn | |
Prints the value of Logn in reverse order |
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 0-31 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Question 265 |
abc x+def^^- | |
abc xde^f^- | |
ab +c xd -e^f ^ | |
-+ a x bc ^^def |
⟶ left to right
Step 1: abc+

Question 266 |
What rotation to make | |
if all childs nodes are at same level | |
when the last rotation occurred | |
if the tree is unbalanced |
Question 267 |
log 2 n nodes | |
n+1 nodes | |
2n nodes | |
2n+1 nodes |
● In a binary tree - a tree where each non-leaf node has exactly two sons - number of leaves is n+1. Total number of nodes is 2n+1.
Full Binary Tree:

In the above tree,non-leaf nodes are 7 so total nodes are 2x7+1=15
Question 268 |
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 |

10, 8, 7, 3, 2, 1, 5.
Question 269 |
Both operations can be performed in O(1) time |
Question 270 |
O(logn) | |
O(n) | |
O(nlogn) | |
O(n 2 ) |
Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)
Note: We can also insert all the elements once, there will be no difference on time complexity.
But according GATE solution they given possibility-1.
Question 271 |
O(log 2 n) | |
O(nlog 2 n) | |
O(n) |
Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply maxheapify.
Question 272 |
no pointer | |
1 pointer | |
2 pointer | |
3 pointer |
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
Question 273 |
is far less than one | |
equals one | |
is far greater than one | |
none of these |
Load factor= n / k
where
● n is the number of entries occupied in the hash table.
● k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)
The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1
Question 274 |
6 | |
5 | |
4 | |
3 | |
None of the above |
Question 275 |
O(n) | |
O(m+n) | |
O(n^2) | |
O(mn) |
Question 276 |
nk | |
(n-1)k+1 | |
n(k-1)+1 | |
n(k-1) |
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1
Question 277 |
Binary search | |
Linear Search | |
Insertion sort | |
Merge Sort |
→ Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
→ Insertion sort & Linear search can use linked list. Note:But Binary search also can implement using linked list but it takes O(n) time complexity.
Question 278 |
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 279 |
!2n / (!n*!(n+1)) | |
C(n,2n) (n+1) | |
!n*C(2n,n) (n+1) | |
C(2n,n)/ !n |
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
Question 280 |
3 | |
4 | |
5 | |
6 |
37%7=2
38%7=3
72%7=2. Here, collision happened because already index 2 is already filled by 37.
According to linear probing, increment index value by 1.
2+1=3 but index 3 also filled with 38 element. So, again increment by 1.
72%7=2( getting index position in hash table 4 )
48%7=6
98%7=0
11%7=4. Here, collision happened because already index 4 is already filled by 72.
According to linear probing, increment index value by 1.
11%7=4 (getting index position in hash table 5 )
56%7=0Here, collision happened because already index 0 is already filled by 98.
According to linear probing, increment index value by 1.
56%7=0 (getting index position in hash table 1 )
Question 281 |
postorder | |
preorder | |
inorder | |
none of these |
Pre order: The root node is visited first, then the left subtree and finally the right subtree.
Post order: First we traverse the left subtree, then the right subtree and finally the root node.
Question 282 |
5,4,10,8,6,49,31,43,19,17,11 | |
4,5,6,8,10,11,19,17,43,31,49 | |
4,5,8,10,6,17,31,49,43,19,11 | |
5,4,10,8,6,17,31,49,43,19,11 |

Post order: 5,4,10,8,6,17,31,49,43,19,11
Question 283 |
0.45 | |
0.5 | |
0.3 | |
0.37(approximately) |
So, 1- (100*99*98*97*96*95*94*93*92*91)/100 10 ⇒ 0.37(approximately)
Question 284 |
B+ tree | |
Threaded binary tree | |
Heap | |
AVL tree |
Question 285 |
Pass by value | |
Pass by name | |
Pass by reference | |
Pass by pointer |
Pass by reference: An alias or reference to the actual parameter is passed to the method.Passing a pointer to the actual parameter, and indirect through the pointer
Pass by name: re-evaluate the actual parameter on every use. For actual parameters that are simple variables, this is the same as call by reference. For actual parameters that are expressions, the expression is re-evaluated on each access.
There is no parameter passing method with the name “ Pass by pointer”
Question 286 |
A+i*N*S | |
A+(i*N+j)*S | |
A+(i*N+j*M)*S | |
A+(i*M+j*N)*S |
M is number of the rows and N is number of Columns and S is size of the element.
The elements are storing row major order. So the elements are in the following order.
A[1,1],A[1,2],A[1,3] ….. A[1,N]
A[2,1],A[2,2],A[2,3]........A[2,N]
……
….
A[M,1],A[M,2],A[M,3]........A[M,N]
We will get the location of A[i,j] by using formula A+(i*N+j)*S where “i” is the index of the row and “j” index of the column and “N” is number of columns.
Question 287 |
In a ternary tree, the number of internal nodes of degree 1,2 and 3 is 4,3 and 3 respectively. The number of leaf nodes in the ternary tree is
11 | |
12 | |
10 | |
9 |
Number of leaf nodes = Sum of degrees of all internal nodes - number of internal nodes +1
= (4*1 + 3*2 + 3*3 ) - 10 + 1
= 19 - 10 + 1
= 10
Formula: nd - n + 1 where n is number of nodes and d is degree of the tree.
Question 288 |
An attribute A of data type varchar(20) has the value ‘xyz’ and attribute B of data type char(20) has the value “Imnop” , then the attribute A has ________ spaces and attribute B has ________ spaces.
20, 20
| |
3, 20 | |