Algorithms
Question 1 
4  
5  
6  
7 
If r = 2
If r = 3
If r = 4
If r = 5
Question 2 
16  
17  
18  
19 
V_{opt} is clearly = 60
For V_{greedy} 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 V_{greedy} = 44
∴ V_{opt} –V_{greedy} = 60 – 44 = 16
Question 3 
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(log_{2} 31) = 4.954196310386876 ⇒ here we are using ceiling so it becomes 5
Question 4 
Step1: Take n=2048 or 2^{11} (Always take n is very big number)
Step2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step3: 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
→ log_{2} 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 5 
(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 6 
(I) only  
(II) only  
both (I) and (II)  
neither (I) nor (II) 
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.
StatementII: 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 7 
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 θ(2^{n}) 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 2^{n}1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log_{2} n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n^{2})
Question 8 
Θ(loglogn)  
Θ(logn)  
Θ(√n)  
Θ(n) 
(or)
T(n)=2T(n^{(1⁄2)} )+1
Here Assume n=2^{k}
T(2^{k} )=2T(2^{k} )^{(1⁄2)}+1
T(2^{k} )=2T(2^{(k/2)} )+1
Assume T(2^{k} )=S(k)
S(k)=2S(k/2)+1
Apply Master’s theorem Case1
a=2,b=2
S(k)=k^{(log22 )}
S(k)=θ(k')
but S(k)=T(2^{k})
T(2^{k})=θ(k')
but n=2^{k}
k=logn
T(n)=θ(logn)
Question 9 
Θ(n√n)  
Θ(n^{2} )  
Θ(n logn)  
Θ(n^{2} 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 10 
225  
226  
227  
228 
General procedure to solve Huffman coding problem
Step1: Arrange into either descending/ ascending order according to that profits.
Step2: Apply optimal merge pattern procedure.
Step3: Make left subtree value either 0 or 1, for right subtree, viceversa.
=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 11 
Θ(nlogn),Θ(nlogn),and Θ(n^{2})  
Θ(n^{2} ),Θ(n^{2} ),and Θ(nlogn)  
Θ(n^{2}),Θ(nlogn),and Θ(nlogn)  
Θ(n^{2}),Θ(nlogn),and Θ(n^{2}) 
Question 12 
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 13 
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 PQ=5, QR=6, RS=8, SP=9, PR=7. When we are forming a cycle RSPR. PR is the lightest edge of the cycle. The MST abcd with cost 11 PQ + QR + RS does not include it.
Statement2: 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 14 
Greedy paradigm.  
DivideandConquer paradigm.  
Dynamic Programming paradigm.  
Neither Greedy nor DivideandConquer nor Dynamic Programming paradigm. 
→ 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 15 
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(n1)+O(n) with the help of substitution method it will take O(n^{2}).
→ 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 16 
1500  
1501  
1502  
1503 
1. ((A_{1}A_{2})A_{3})A_{4}
2. ((A_{1}(A_{2}A_{3}))A_{4})
3. (A_{1}A_{2})(A_{3}A_{4})
4. A_{1}((A_{2}A_{3})A_{4})
5. A_{1}(A_{2}(A_{3}A_{4})).
→ A_{1}((A_{2}A_{3})A_{4}) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
Question 17 
2.3219280  
2.3219281  
2.3219282  
2.3219283 
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>b^{k} case
A(n)=n^{(logba )}=n^{(log25 )}=n^{2.3219280}
∴α=2.3219280
Question 18 
T(n) = 2T (n/2) + cn
 
T(n) = T(n – 1) + T(1) + cn  
T(n) = 2T (n – 2) + cn
 
T(n) = T(n/2) + cn

Question 19 
Piii, Qii, Riv, Si
 
Pi, Qii, Riv, Siii
 
Pii, Qiii, Riv, Si  
Pii, Qi, Riii, Siv 
Floydwarshall 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 20 
An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decreasekey 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 decreasekey 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  
Minheap  
Sorted array  
Sorted doubly linked list 
Question 21 
69  
70  
71  
72 
⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
Question 22 
1i, 2iii, 3i, 4v.  
1iii, 2iii, 3i, 4v.  
1iii, 2ii, 3i, 4iv.  
1iii, 2ii, 3i, 4v. 
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. It takes worst case time complexity is O(V3) and worst case space complexity is O(V2).
→ 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 Depthfirst search
Question 23 
(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 24 
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 × 10^{6}B  1s
512 B  512B/ 50×10^{6}B/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 25 
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 = 2^{9} × 9
So for n = 2^{9}, it satisfies.
So, n = 2^{9} = 512
Question 26 
995  
996  
997  
998 
Question 27 
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 28 
Question 29 
148  
149  
150  
151 
Question 30 
Θ(n)  
Θ(nlog n)  
Θ(n^{2})  
Θ(logn) 
Apply Master’s theorem,
a=2,b=2,k=0,p=1
According to Master’s theorem, we can apply CaseI
(I) If a>b^{k}, then T(n)=θ(n^{(logba )} ) =θ(n^{(log22 )} )= θ (n)
Question 31 
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 32 
358  
359  
360  
361 
In the above implementation, total number of comparisons is
(441) + (941) + (651) + (1591) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n1.
Question 33 
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 34 
SQPTRWUV  
SQPTUWRV  
SQPTWUVR  
SQPTRUWV 
Inorder Traversal: Left, Root, Middle, Right.
Question 35 
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 36 
O(n^{2})  
O(n log n)  
Θ(n logn)  
O(n^{3}) 
Question 37 
110  
111  
112  
113 
1. n_{1} is the smallest number greater than or equal to L and there is no predecessor n_{1}' of >n_{1} such that n_{1}' is equal to n_{1}.
2. n_{2}2' of n_{2} such that is equal to n_{2}.
Since there are m elements between n_{1} and n_{2}, it takes ‘m’ time to add all elements between n_{1} and n_{2}.
So time complexity is O(log n+m)
So the given expression becomes O(n^{0}log'n+m'log^{0}n)
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 38 
(97×97×97)/100^{3}  
(99×98×97)/100^{3}  
(97×96×95)/100^{3}  
(97×96×95)/(3!×100^{3}) 
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))⁄100^{3}
Question 39 
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 subtree 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 40 
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 41 
O(log n)  
O(n)  
O(n log n)  
O(n^{2}) 
Selection sort time complexity O(n^{2}) in terms of number of comparisons. Each of these scans requires one swap for n1 elements (the final element is already in place).
Question 42 
O(1)  
O(log n)  
O(n)  
O(n log n) 
Question 43 
{є}  
ϕ  
a*  
{є,a} 
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 44 
Θ(n^{2})  
Θ(n^{2} log n)  
Θ(n^{3})  
Θ(n^{3} 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(n1)/2=(n^{3})
Question 45 
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 = ^{8}C_{3} = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
Question 46 
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 47 
Θ(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 48 
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=x^{4}
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=9^{4}=6561
Question 49 
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 50 
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 ≤ 3v  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 51 
Θ(n)  
Θ(n + k)  
Θ(nk)  
Θ(n^{2}) 
i. One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be Ѳ(n).
or
ii. We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any permutation of Enqueues and Dequeues totaling ‘n’ times. Completity will be Ѳ(n).
or iii. We can perform Enqueues and MultiDequeues. A general pattern could be as follows: Enqueue Enqueue …(ktimes) MultiDequeue Enqueue Enqueue …(ktimes) MultiDequeue …Up to total n …. K items enqueued ….k items deleted….k items enqueued…..k items deleted  and so on.
The number of times this kEnqueues, MultiDequeue cycle is performed = n/k+1
So, Complexity will be k times Enqueue + 1 MultiDequeue) ×n/k+1
Which is (2k×n/k+1) = (n)
or
iv. We can just perform n MultiDequeues (or n Dequeues for the matter):
Each time the while condition is false (empty queue), condition is checked just once for each of the ‘n’ operations. So Ѳ(n).
Question 52 
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 53 
NPcomplete = NP  
NPcomplete ∩ P = ∅  
NPhard = NP  
P = NPcomplete 
The definition of NPcomplete is,
A decision problem p is NPcomplete 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 NPcomplete ∩ P = ∅ .
This is due to the fact that, if NPcomplete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NPcomplete also, then it means that P1 (NPcomplete 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 NPcomplete 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 54 
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

Question 55 
Q solves the subsetsum problem in polynomial time when the input is encoded in unary
 
Q solves the subsetsum 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 NPhard

Note: As per Present GATE syllabus , the above concept is not required.
Question 56 
only vertex a  
only vertices a, e, f, g, h
 
only vertices a, b, c, d
 
all the vertices 
AB ⇒ 1
AC⇒ 1+2=3
AE⇒ 13 =2
AF⇒ 1 3 +2 =0
AG⇒ 1 3 +2 +3 =3
AC ⇒1 +2 =3
AH⇒ 1+2 5 =2
Question 57 
p  
p + 1  
n  p  
n  p + 1 
RST contains elements = p
Root contains = 1 element
1^{st} contains = n  (p + 1) element
Root contains the value is n  p.
Question 58 
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 = np
p = n  k
Question 59 
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)
FloydWarshall algorithm → O(n^{3})
Topological sorting → O(n+m)
Question 60 
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 61 
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:
2^{h1}  
2^{h1} + 1  
2^{h}  1  
2^{h} 
Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 62 
Divide and conquer strategy  
Backtracking approach  
Heuristic search  
Heuristic search 
Question 63 
O(m)  
O(n)  
O(m+n)  
O(logm+logn) 
In worst case, no. of comparisons is m+n1.
Then we require O(m+n) comparisons to merging two sorted lists.
Question 64 
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 65 
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 66 
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 67 
∴
Question 68 
Dynamic programming  
Backtracking  
Divide and conquer  
Greedy method 
Question 69 
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:
Callbyreference = 8
Callbyvalue = 1
Question 70 
Optimal binary search tree construction can be performed efficiently using dynamic programming.  
Breadthfirst 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.  
Depthfirst search can be used to find connected components of a graph. 
Question 71 
g_{1}(n) is O(g_{2}(n))  
g_{1} (n) is O(^{3})  
g_{2} (n) is O(g_{1} (n))  
g_{2} (n) is O(n)  
Both A and B 
Growth rate of g_{1} is less than that of g_{2} i.e., g_{1}(n) = O(g_{2}(n)) = O(n).
Question 72 
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 73 
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 74 
O(n)  
O(n^{2})  
O(n^{3})  
O(3n^{2})  
O(1.5n^{2})  
B, C, D and E 
⇒ In this 'n' is constant. So, n is added to n times itself which is O(n^{2}).
Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.
Question 75 
O(m log n) 
Question 76 
Heapsort  
Quicksort  
Mergesort  
Radixsort 
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
Question 77 
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.
n 
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
Question 78 
7 
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
Question 80 
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 82 
O(n^{2})  
O(mn)  
O(m+n)  
O(m logn)  
O(m^{2})  
B, D and E 
→ Where m is no. of edges and n is number of vertices then n = O(m^{2})
→ O(m logn) < O(mn)
Question 83 
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