Algorithms
Question 1 |
Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)
19 | |
39 | |
29 | |
09 |
Ex: {A,B,C,D}
{ A,AB,AC,AD,ABC,ABD,ACD,
B, BC,BD,BCD,
C,CD,
D }
Step-1: Array of elements A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0 ]
Step-2: As per the given question, if they want to find maximum subsequence means
{6,3,13,4,4,12}
= 42
Step-3: But according to given recurrence relation, the sequence should be continuous. {6,3,13,4,4,12}.
This is not continuous subsequence.
Step-4: The continuous sequence is {6, 3, -1, -2, 13, 4, -9, -1, 4, 12}
Total is {29}
Note: We can't get more than 29 maximum subsequence sum.
Question 2 |
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _____.
0.08 | |
0.01 | |
1 | |
8 |
Step-2: Pivot element = uniformly random.
Step-3: Worst case position in the pivot element is either first (or) last.
Step-4: So total 2 possibilities among 25 distinct elements
= 2/25
= 0.08
Question 3 |
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) timeWhich 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 4 |
There are n unsorted arrays: A1, A2, ..., An. Assume that n is odd. Each of A1, A2, ..., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, ..., An is
O(n) | |
O(n log n) | |
Ω(n2 log n) | |
O(n2) |
But it is similar to quicksort but in quicksort, partitioning will take extra time.
→ Find the median will be (i+j)/2
1. If n is odd, the value is Ceil((i+j)/2)
2. If n is even, the value is floor((i+j)/2)
-> Here, total number of arrays are
⇒ O(n)*O(n)
⇒ O(n2)
Note:
They are clearly saying that all are distinct elements.
There is no common elements between any two arrays.
Question 5 |
I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.Which of the above statements is/are TRUE?
I only | |
II only | |
Both I and II | |
Neither I nor II |
I. TRUE: G Graph is unique, no two edges of the graph is same.

Step-1: Using Kruskal's algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step-2:

Step-3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147
Step-4: Here, all the elements are distinct. So, the possible MCST is 1.
II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.
Because we are already given, all minimum edge weights if graph is distinct.
Question 7 |
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 | |
![]() | |
![]() | |
for every f:V--> R
|

Question 8 |
![]() | |
![]() | |
![]() | |
![]() |
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge .
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V)
Method-2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method-1 is the most appropriate answer for giving a question.
Question 9 |
99 |
• N =100
• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So 99 edges of weight is 99
Question 10 |
Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _________.
4 | |
5 | |
6 | |
7 |
If x = 5 then the total number of MWSTs are 4.
If r = 1

If r = 2

If r = 3

If r = 4

If r = 5


Question 11 |
Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy.
The value of Vopt − Vgreedy is ______ .
16 | |
17 | |
18 | |
19 |

Vopt is clearly = 60
For Vgreedy use the table (Do not take the fraction as per the question),
Item 4 picked,
Profit = 24
Remaining weight = 11 – 2 = 9
Next item 3 picked (item 1 cannot be picked since its capacity is greater than available capacity),
Profit = 24 + 20 = 44
Remaining capacity = 9 – 4 = 5
Now no item can be picked with available capacity.
So Vgreedy = 44
∴ Vopt – Vgreedy = 60 – 44 = 16
Question 12 |
Consider the following functions from positives integers to real numbers
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
![]() | |
![]() | |
![]() | |
![]() |
Step-1: Take n=2048 or 211 (Always take n is very big number)
Step-2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step-3: The above functions are belongs to polynomial. So, simply substitute the value of n,
First compare with constant values.
→ 100 / 2048 = 0.048828125
→ 10 > 100/ 2048
→ log2 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 13 |
(P)↔(ii), Q↔(iii), (R)↔(i) | |
(P)↔(iii), Q↔(i), (R)↔(ii) | |
(P)↔(ii), Q↔(i), (R)↔(iii) | |
(P)↔(i), Q↔(ii), (R)↔(iii) |
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.
Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc..,
Question 14 |
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
-
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) only | |
(II) only | |
both (I) and (II) | |
neither (I) nor (II) |
Let us take an example

Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:

Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
Statement-II: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.
Question 15 |
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________.
5 | |
6 | |
7 | |
8 |
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
So number of probes = ceil(log2 31) = 4.954196310386876
⇒ here we are using ceiling so it becomes 5
Question 16 |
Match the algorithms with their time complexities:
Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ(n2) (Q) Binary search given n stored numbers (ii) Θ(n log n) (R) Heap sort given n numbers at the worst case (iii) Θ(2n) (S) Addition of two n×n matrices (iv) Θ(log n)
P→(iii), Q→(iv), R→(i), S→(ii) | |
P→(iv), Q→(iii), R→(i), S→(ii) | |
P→(iii), Q→(iv), R→(ii), S→(i) | |
P→(iv), Q→(iii), R→(ii), S→(i) |
→ Tower of Hanoi with n disks takes θ(2n) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)
Question 17 |
Θ(loglogn) | |
Θ(logn) | |
Θ(√n) | |
Θ(n) |
(or)
T(n) = 2T(n(1⁄2)) + 1
Here, Assume n = 2k
T(2k) = 2T(2k)(1⁄2) + 1
T(2k) = 2T(2(k/2) ) + 1
Assume T(2k) = S(k)
S(k) = 2S(k/2) + 1
Apply Master’s theorem Case-1
a=2, b=2
S(k) = k(log22 )
S(k) = θ(k')
but S(k) = T(2k)
T(2k) = θ(k')
but n = 2k
k = logn
T(n) = θ(logn)
Question 18 |
Consider the following C function.
int fun (int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j < n; j += i) { printf("%d %d",i,j); } } }
Time complexity of fun in terms of Θ notation is
Θ(n√n) | |
Θ(n2 ) | |
Θ(n logn) | |
Θ(n2 logn) |
int fun(int n)
{
int i, j;
for (i = 1; i <= n ; i++) /* It is independent loop. So, it takes O(n) time */
{
for (j = 1; j < n; j += i) /* It is dependent loop, It always incrementing with the help of i. It will take approximately O(log n) times*/
{
printf("%d %d", i, j); /* It takes O(1) time */
}
}
}
So, the overall complexity of the program is θ(n logn) times.
Question 19 |
A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.
225 | |
226 | |
227 | |
228 |

General procedure to solve Huffman coding problem
Step-1: Arrange into either descending/ ascending order according to that profits.
Step-2: Apply optimal merge pattern procedure.
Step-3: Make left sub-tree value either 0 or 1, for right sub-tree, vice-versa.




= 2 × 0.34 + 2 × 0.22 + 2 × 0.19 + 3 × 0.17 + 3 × 0.08
= 2.25
∴ So, for 100 characters, 2.25 * 100 = 225
Question 20 |
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Θ(nlogn), Θ(nlogn), and Θ(n2) | |
Θ(n2 ), Θ(n2 ), and Θ(nlogn) | |
Θ(n2), Θ(nlogn), and Θ(nlogn) | |
Θ(n2), Θ(nlogn), and Θ(n2) |

Question 21 |
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is __________.
7 | |
8 | |
9 | |
10 |

Now consider vertex A to make Minimum spanning tree with Maximum weights.
As weights are 1, 2, 3, 4, 5, 6. AB, AD, AC takes maximum weights 4, 5, 6 respectively.
Next consider vertex B, BA = 4, and minimum spanning tree with maximum weight next is BD & BC takes 2, 3 respectively.
And the last edge CD takes 1.
So, 1+2+4 in our graph will be the Minimum spanning tree with maximum weights.
Question 22 |
G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
-
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
I only | |
II only | |
both I and II | |
neither I nor II |
The MSTs of G may or may not include the lightest edge.
Take rectangular graph labelled with P,Q,R,S.
Connect with P-Q = 5, Q-R = 6, R-S = 8, S-P = 9, P-R = 7.
When we are forming a cycle R-S-P-R. P-R is the lightest edge of the cycle.
The MST abcd with cost 11
P-Q + Q-R + R-S does not include it.
Statement-2: True
Suppose there is a minimum spanning tree which contains e. If we add one more edge to the spanning tree we will create a cycle.
Suppose we add edge e to the spanning tree which generated cycle C.
We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal which implies that e must not be in minimum spanning tree and we get a contradiction.
Question 23 |
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
-
I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
I and II only | |
I and III only | |
II and IV only | |
I and IV only |
→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n-1)+O(n) with the help of substitution method it will take O(n2).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n) with the help of substitution method it will take O(nlogn).
We can also use master's theorem [a=2, b=2, k=1, p=0] for above recurrence.
Question 24 |
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
Greedy paradigm. | |
Divide-and-Conquer paradigm. | |
Dynamic Programming paradigm. | |
Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm. |
It takes worst case time complexity is O(|V|3) and worst case space complexity is O(|V|2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices.
Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
Question 25 |
Let A1, A2, A3 and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is _________.
1500 | |
1501 | |
1502 | |
1503 |
The optimal parenthesized sequence is A1((A2A3)A4) out of many possibilities, the possibilities are
1. ((A1A2)A3)A4
2. ((A1(A2A3))A4)
3. (A1A2)(A3A4)
4. A1((A2A3)A4)
5. A1(A2(A3A4))
→ A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
Question 26 |
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(nα), then the least possible value (accurate upto two decimal positions) of α is _________.

2.3219280 | |
2.3219281 | |
2.3219282 | |
2.3219283 |
According to flow chart total 5 worst case possibilities of function calls.

The remaining function calls/return statements will execute only constant amount of time.
So, total function calls 5.
The Recurrence will be
A(n) = 5A(n/2) + O(1)
Apply Master’s theorem,
A=5, b=2, k=0, p=0
a > bk case
A(n) = n(logba ) = n(log25) = n2.3219280
∴α = 2.3219280
Question 27 |
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.
T(n) = 2T(n/2) + cn
| |
T(n) = T(n – 1) + T(1) + cn | |
T(n) = 2T(n – 1) + cn
| |
T(n) = T(n/2) + cn
|
Hence recurrence relation T(n) = T(n - 1) + T(1) + cn.
Question 28 |
P-iii, Q-ii, R-iv, S-i
| |
P-i, Q-ii, R-iv, S-iii
| |
P-ii, Q-iii, R-iv, S-i | |
P-ii, Q-i, R-iii, S-iv |
Floyd-warshall always changes it distance at each iteration which is nothing but dynamic programming.
Merge sort in merge sort first we always divide and merge to perform sorting hence divide and conquer.
Hamiltonian circuit used to reach the entire vertex once, if some vertex is repeating in its path it will backtrack.
Question 29 |
An algorithm performs (log N)1/2 find operations, N insert operations, (log N)1/2 delete operations, and (log N)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?
Unsorted array | |
Min-heap | |
Sorted array | |
Sorted doubly linked list |

Question 30 |

69 | |
70 | |
71 | |
72 |

⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
Question 31 |
1-i, 2-iii, 3-i, 4-v. | |
1-iii, 2-iii, 3-i, 4-v. | |
1-iii, 2-ii, 3-i, 4-iv. | |
1-iii, 2-ii, 3-i, 4-v. |
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. It takes worst case time complexity is O(|V|3) and worst case space complexity is O(|V|2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
(3) Binary search on a sorted array:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
(4) Backtracking search on a graph uses Depth-first search
Question 32 |
(a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1)
| |
(a, left_end, k) and (a, n – left_end – 1, k – left_end – 1)
| |
(a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k)
| |
(a, n – left_end – 1, k – left_end – 1) and (a, left_end, k)
|
Question 33 |
6 | |
6.1 | |
6.2 | |
6.3 |
1 rotation → 60 /15000 sec = 4 ms
∴ Average rotational delay = 1/2 × 4 ms = 2 ms
Average seek time = 2 × Average rotational delay
= 2 × 2 ms = 4 ms
Time to transfer 512 byte,
50 × 106B ------- 1s
512 B ------- 512B/ 50×106B/s = 0.01 ms
∴ Controllers transfer time
= 10 × Disk transfer time
= 10 × 0.01 ms
= 0.01 ms
∴ Avg. time = (4 + 2 + 0.1 + 0.01)ms
= 6.11 ms
Question 34 |
256 | |
512 | |
1024 | |
2048 |
where c is some constant
It is given that for n = 64,
cn log n = 30
c × 64 log 64 = 30
c × 64 × 6 = 30
c = 5/64
Now, the value of n for
c n log n = 360
5/64 × n log n = 360
n log n = 360×64/5
= 72 × 64 = 29 × 9
So for n = 29, it satisfies.
So, n = 29 = 512
Question 35 |
995 | |
996 | |
997 | |
998 |
Question 36 |
12 | |
13 | |
14 | |
15 |
No. of coins picked: 1 2 4 8 16
There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.
Let there be x number of 10gm coins and y number of 11gm coins.
So, 10x + 11y = 323 ------ (1)
And we also know that total number of coins picked is
1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,
= 31 ------ (2)
Solving equation (1) and (2), we get
y = 13
Means total there are 13 coins of 11gm.
Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.
So product of labelled bag number = 1×3×4 = 12
Question 37 |
![]() | |
![]() | |
![]() | |
![]() |
Question 38 |
148 | |
149 | |
150 | |
151 |
Question 39 |
T(n) = 2T(n/2) + Logn
Θ(n) | |
Θ(nlog n) | |
Θ(n2) | |
Θ(logn) |
Apply Master’s theorem,
a=2,b=2,k=0,p=1
According to Master’s theorem, we can apply Case-I
(I) If a>bk, then T(n)=θ(n(logba ) ) =θ(n(log22 ) )= θ (n)
Question 40 |
34 | |
35 | |
36 | |
37 |
A = “qpqrr” B = “pqprqrp”
The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:
(1) qpqr
(2) pqrr
(3) qprr
So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34
Question 41 |
358 | |
359 | |
360 | |
361 |

In the above implementation, total number of comparisons is
(44-1) + (94-1) + (65-1) + (159-1) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.
Question 42 |
6 | |
7 | |
8 | |
9 |

Minimum Spanning Tree:

From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.
So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.
Question 43 |

SQPTRWUV | |
SQPTUWRV | |
SQPTWUVR | |
SQPTRUWV |

Inorder Traversal: Left, Root, Middle, Right.
So, durig inorder traversal whenever we visit the node second time then print it.
So, output will be,
S Q P T R W U V
Question 44 |

19 | |
20 | |
21 | |
22 |

Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.

Question 45 |
O(n2) | |
O(n log n) | |
Θ(n logn) | |
O(n3) |
Question 46 |
110 | |
111 | |
112 | |
113 |
1. n1 is the smallest number greater than or equal to L and there is no predecessor n1' of >n1 such that n1' is equal to n1.
2. n22' of n2 such that is equal to n2.
Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.
So time complexity is O(log n+m)
So the given expression becomes O(n0log'n+m'log0n)
And a+10b+100c+1000d=0+10*1+100*1+1000*1=10+100=110
Because a=0, b=1, c=1 and d=0
Question 47 |
(97×97×97)/1003 | |
(99×98×97)/1003 | |
(97×96×95)/1003 | |
(97×96×95)/(3!×1003) |
They are picked with equal probability of Hash function since it is uniform hashing.
So to avoid the first 3 slots to be unfilled
=97/100*97/100*97/100=((97*97*97))⁄1003
Question 48 |
number of internal nodes in the tree. | |
height of the tree. | |
number of nodes without a right sibling in the tree. | |
number of leaf nodes in the tree. |
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.
Question 49 |
It will run into an infinite loop when x is not in listA. | |
It is an implementation of binary search. | |
It will always find the maximum element in listA. | |
It will return −1 even when x is present in listA. |
k = (i+j)/2;
where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.
So it is an implementation of Binary search.
Question 50 |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) |
Selection sort time complexity O(n2) in terms of number of comparisons. Each of these scans requires one swap for n-1 elements (the final element is already in place).
Question 51 |
O(1) | |
O(log n) | |
O(n) | |
O(n log n) |
Question 52 |
{є} | |
ϕ | |
a* | |
{є,a} |
Rϕ = ϕR=ϕ
So L1 L2 * = ϕ
and L1 * = {ϕ}* = {ϵ}
So L1L2* ∪ L1* = {ϵ}
Question 53 |
Θ(n2) | |
Θ(n2 log n) | |
Θ(n3) | |
Θ(n3 log n) |
Bellman–Ford runs in O(|V| * |E|) time, where |V| and |E| are the number of vertices and edges respectively.
Note: For complete graph: |E| = n(n-1)/2 = O(n2)
Question 54 |
1/8 | |
1 | |
7 | |
8 |

The probability that there exists one edge between two vertices = 1/2

So, the total probability that all three edges of the above exists
= 1/2 × 1/2 × 1/2 (as they are independent events)
= 1/8
Total number of ways in which we can select ‘3’ such vertices among ‘8’ vertices = 8C3 = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
Question 55 |
P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
P only | |
Q only | |
Both P and Q | |
Neither P nor Q |
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 56 |
(P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
P only | |
P and R only | |
R only | |
P, Q and S only |
R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar,
|E| ≤ 3|v| - 6
For 9 vertices |E| ≤ 3 × 9 - 6
⇒ |E| ≤ 27 - 6
⇒ |E| ≤ 21. But L(G) has 25 edges and so is not planar.
As (R) is false, option (B) & (C) are eliminated.
Question 57 |
Θ(1) | |
Θ(√logn) | |
Θ (logn/loglogn) | |
Θ(log n) |
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn - log log logn))
= Θ((log n/log logn) × log log n)
= Θ (log n)
Hence, option (C) is correct answer.
Question 58 |
int f( int &x, int c) { c = c - 1; if (c==0) return 1; x = x + 1; return f(x,c) * x; } |
3024 | |
6561 | |
55440 | |
161051 |
f(5,5)→f(x,4)*x
f(x,3)*x*x
f(x,2)*x*x*x

⇒x*x*x*x=x4
Now x=x+1, there are 4 different calls namely f(6,4),f(7,3),f(8,2),f(9,1)
Because of pass by reference, x in all earlier functions is replaced with 9.
⇒ 9*9*9*9=94=6561
Question 59 |
10, 20, 15, 23, 25, 35, 42, 39, 30 | |
15, 10, 25, 23, 20, 42, 35, 39, 30 | |
15, 20, 10, 23, 25, 42, 35, 39, 30 | |
15, 10, 23, 25, 20, 35, 42, 39, 30 |

From the data,

The Postorder traversal sequence is:
→ 15, 10, 23, 25, 20, 35, 42, 39, 30.
Question 60 |
MultiDequeue(Q){ m = k while (Q is not empty and m > 0) { Dequeue(Q) m = m - 1 } }What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue? (GATE CS 2013)
Θ(n) | |
Θ(n + k) | |
Θ(nk) | |
Θ(n2) |
Question 61 |
NP-complete = NP | |
NP-complete ∩ P = ∅ | |
NP-hard = NP | |
P = NP-complete |
The definition of NP-complete is,
A decision problem p is NP-complete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
Question 62 |
A(n) = Ω (W(n)) | |
A(n) = Θ (W(n)) | |
A(n) = O (W(n)) | |
A(n) = o (W(n)) |
So, A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort).
A(n)=O(W(n))
Note: Option A is wrong because A(n) is not equal to Ω(w(n)) .
Question 63 |
T(n) ≤ 2T(n/5) + n
| |
T(n) ≤ T(n/5) + T(4n/5) + n
| |
T(n) ≤ 2T(4n/5) + n | |
T(n) ≤ 2T(n/2) + n
|
So, T(n/5) comparisons are needed for the first subset and T(4n/5) comparisons needed for second subset.
Now, suppose that one subset contains more than n/5 elements then another subset will contain less than 4n/5 elements. Due to which time complexity will be less than
T(n/5) + T(4n/5) + n
Because recursion tree will be more balanced.
Question 64 |
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
| |
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
| |
The subset sum problem belongs to the class NP | |
The subset sum problem is NP-hard
|
Question 65 |

only vertex a | |
only vertices a, e, f, g, h
| |
only vertices a, b, c, d
| |
all the vertices |
A-B ⇒ 1
A-C⇒ 1+2=3
A-E⇒ 1-3 =-2
A-F⇒ 1 -3 +2 =0
A-G⇒ 1 -3 +2 +3 =3
A-C ⇒1 +2 =3
A-H⇒ 1+2 -5 =-2
Question 66 |
p | |
p + 1 | |
n - p | |
n - p + 1 |
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element

Root contains the value is n - p.
Question 67 |
k | |
k + 1 | |
n - k - 1 | |
n - k |
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
Question 68 |
1. Bellman-Ford algorithm 2. Kruskal’s algorithm 3. Floyd-Warshall algorithm 4. Topological sorting | A : O ( m log n) B : O (n3) C : O (nm) D : O (n + m) |
1→ C, 2 → A, 3 → B, 4 → D | |
1→ B, 2 → D, 3 → C, 4 → A | |
1→ C, 2 → D, 3 → A, 4 → B | |
1→ B, 2 → A, 3 → C, 4 → D |
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
Question 69 |
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?
2 | |
3 | |
4 | |
6 |
165%10 = 5 [occupy 5]
62%10 = 2 [occupy 2]
123%10 = 3 [3 already occupied, so occupies 4]
142%10 = 2 [2, 3, 4, 5 are occupied, so it occupies 6]
Question 70 |
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:
2h-1 | |
2h-1 + 1 | |
2h - 1 | |
2h |

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 71 |
T(n) = θ(log n) | |
T(n) = θ(√n) | |
T(n) = θ(n) | |
T(n) = θ(n log n) |
Question 72 |
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight | |
There exists a cycle in G having all edges of maximum weight | |
Edge e cannot be contained in a cycle | |
All edges in G have the same weight
|

(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
Question 73 |
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be
8, 7, 6, 5, 4, 3, 2, 1 | |
1, 2, 3, 4, 8, 7, 6, 5 | |
2, 1, 4, 3, 6, 7, 8, 5 | |
2, 1, 4, 3, 7, 8, 6, 5 |
5, 3, 1, 2, 4, 6, 8, 7
In-order is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,

Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
Question 74 |
4 | |
7 | |
23 | |
99 |
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
Question 75 |

5 | |
4 | |
3 | |
2 |
Question 76 |
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/2⌋, ....., 0. The time required to construct a heap in this manner is
O(log n) | |
O(n) | |
O(n log log n) | |
O(n log n) |
And we know that time complexity for building the heap is O(n)
Question 77 |
![]() | |
![]() | |
![]() | |
![]() |
Left root right.
Preorder traversal is,
Root left right.
Question 78 |
f(n) + g(n) = O(h(n)) + h(n)) | |
f(n) = O(h(n)) | |
fh(n) ≠ O(f(n)) | |
f(n)h(n) ≠ O(g(n)h(n))
|
So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
Question 79 |

(E, G), (C, F), (F, G), (A, D), (A, B), (A, C) | |
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G) | |
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C) | |
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
|
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 80 |
RECURSIVE ALGORITHM | RECURRENCE RELATION | ||
---|---|---|---|
P. | Binary search | I. | T(n) = T(n-k) + T(k) + cn |
Q. | Merge sort | II. | T(n) = 2T(n-1) + 1 |
R. | Quick sort | III. | T(n) = 2T(n/2) + cn |
S. | Tower of Hanoi | IV. | T(n) = T(n/2) + 1 |
P-II, Q-III, R-IV, S-I | |
P-IV, Q-III, R-I, S-II | |
P-III, Q-II, R-IV, S-I | |
P-IV, Q-II, R-I, S-III |
Binary search - T(n/2) + 1
Merge sort - T(n) = 2T(n/2)+ cn
Tower of hanoi - T(n) = 2T(n-1) +1
Question 81 |
Divide and conquer strategy | |
Backtracking approach | |
Heuristic search | |
Heuristic search |
Question 82 |
O(m) | |
O(n) | |
O(m+n) | |
O(logm+logn) |
In worst case, no. of comparisons is m+n-1.
Then we require O(m+n) comparisons to merging two sorted lists.
Question 83 |
AB + CD + *F/D + E* | |
ABCD + *F/DE*++
| |
A *B + CD/F *DE++ | |
A + *BCD/F* DE++ | |
None of the above |
A B C D + * F / + D E * +
Question 84 |
I and II | |
II and III | |
I and IV | |
I and III |
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind ietrative one in terms of performance.
Question 85 |
they use static allocation for variables
| |
they use dynamic allocation for variables | |
stacks are not available on all machines | |
it is not possible to implement recursion on all machines |
→ Recursion requires dynamic allocation of data.
Question 86 |
![]() | |
![]() | |
![]() | |
![]() |
∴

Question 87 |
Dynamic programming | |
Backtracking | |
Divide and conquer | |
Greedy method |
Question 88 |
Passing a constant value as a parameter | |
Passing the address of an array as a parameter | |
Passing an array element as a parameter | |
Passing an array following statements is true
|
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Call-by-reference = 8
Call-by-value = 1
Question 89 |
Optimal binary search tree construction can be performed efficiently using dynamic programming. | |
Breadth-first search cannot be used to find converted components of a graph. | |
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed. | |
Depth-first search can be used to find connected components of a graph. |
Question 90 |
g1(n) is O(g2(n)) | |
g1 (n) is O(3) | |
g2 (n) is O(g1 (n)) | |
g2 (n) is O(n) | |
Both A and B |
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
Question 91 |
at a fixed address in main memory | |
at a fixed location on the disk | |
anywhere on the disk | |
at a fixed location on the system disk | |
anywhere on the system disk |
Question 92 |
G has no cycles. | |
The graph obtained by removing any edge from G is not connected.
| |
G has at least one cycle. | |
The graph obtained by removing any two edges from G is not connected. | |
Both C and D. |
For example let us consider, n=3
Question 93 |
O(n) | |
O(n2) | |
O(n3) | |
O(3n2) | |
O(1.5n2) | |
B, C, D and E |

⇒ In this 'n' is constant. So, n is added to n times itself which is O(n2).
Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.
Question 94 |
O(m log n) |
Question 95 |
Heapsort | |
Quicksort | |
Mergesort | |
Radixsort |
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
Question 96 |
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…..n] are to be sorted, give an input for which Quicksort takes maximum time.
O(n^2) |
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
Question 97 |
7 |
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
Question 99 |
4, 1, 6, 7, 3, 2, 5, 8 |
(Left, Root, Right)
So, the order will be
4, 1, 6, 7, 3, 2, 5, 8
Question 101 |
O(n2) | |
O(mn) | |
O(m+n) | |
O(m logn) | |
O(m2) | |
B, D and E |
→ Where m is no. of edges and n is number of vertices then n = O(m2)
→ O(m logn) < O(mn)
Question 102 |
20, 10, 20, 10, 20 | |
20, 20, 10, 10, 20 | |
10, 20, 20, 10, 20 | |
20, 20, 10, 20, 10 |
→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)
→ PUSH(10), PUSH(10), POP = 10 (iii)
→ PUSH(10), POP = 10 (iv)
→ PUSH(20)
→ PUSH(20), POP = 20 (v)
⇒ 20, 20, 10, 10, 20
Question 103 |
(a) - (r), (b) - (p), (c) - (s), (d) - (q) |
Kruskal's minimum spanning tree algorithm - Greedy method
Biconnected components algorithm - Depth first search
Floyd's shortest path algorithm - Dynamic programming