Previous Year Questions: ARRAY

  Q1: Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array  [2,5,3,1,4,2,6] is _____   (2024 SET-  2)
(a) 1
(b) 2
(c) 3
(d) 4
Ans : (c)
Sol :
Given array: [2, 5, 3, 1, 4, 2, 6]
Indices:  0  1  2  3  4  5  6
Values:   2  5  3  1  4  2  6
The array with sorted indices:
Indices:  0  1  2  3  4  5  6
Values:   2  2  3  3  4  4  6
Number of elements out of order: 3

Q2: What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?  (2021 SET-2) 
(a)
(b)
(c)  
(d)
Ans:(b)
Sol:
Worst-case number of arithmetic operations performed by recursive binary search on a sorted array is given by the following recurrence relation: 

Q3:  Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?  (2021 SET1)
(a)
(b)
(c) 
(d)
Ans: (c)
Sol :
The answer is a stub!

Tournament Method:

• Imagine using merge sort and you'd divided the array elements in pairs of two, every element is compared with each other.
• The largest(or smallest if preferred) is selected out each pairs and the winners are copied to a new array and the procedure it repeated till we have one element remaining.

 For this, 
At first we need  comparisons(since  pairs), then so on this sums to n$n$ , an AP 

• For finding the smallest element we would use the losers left out in the first round  losers to be precise.
• We again use this procedure with an intention for finding smaller amongst all, (worst losers will be the best winners in these rounds, ironical indeed).

For this,
We need, at first since we are pitting losers against losers comparisons then,

so on which sums  upto.
 

The number  of comparisons needed is at least   if we consider the elements to be distinct.

Q4:  If an array A contains the items 10,4, 7,23,67,12 and 5 in that order, what will be the resultant array A after third pass of insertion sort?   (2020)
(a)  67,12,10,5,4,7,23
(b)  4,7,10,23,67,12,5
(c)  4,5,7,67,10,12,23
(d)  10,7,4,67,23,12,5 
Ans:(b)
Sol:

 Pass$1$ will be applied on the first 2 $\mathrm{<br><br>}$elements. 

Q5:  Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of row number and column number. The array is stored in row-major format. If the first element x[0] [0] occupies the memory location with address 1000 and each element occupies only one memory location, which all locations (in decimal) will be holding a value of 10?  (2020)
(a) 1018,1091
(b)  1022,1041
(c)  1017,1036
(d)  1000,1399
Ans: (c)
Sol:  We can only get 10 from following combinations:
1×10 - NOT POSSIBLE (column out of range)
2×5 - NOT POSSIBLE (column out of range)
5×2 - POSSIBLE

Using 1-based indexing:
x[5][2] ⇒ (5×2 = 10)

Convert to 0-based index → x[4][1]

Address calculation (row-major):
x[4][1] = 1000 + (4×4 + 1) = 1000 + 17 = 1017

Similarly, second address from options:
x[9][0] = 1000 + (9×4 + 0) = 1000 + 36 = 1036

Final Answer: (c) 1017, 1036