Previous Year Questions: ARRAY | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

  Q1: Let $A$A be an array containing integer values. The distance of $A$A is defined as the minimum number of elements in $A$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   $\frac{n}{2}$ 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, $\frac{n}{4}$  at first since we are pitting losers against losers comparisons then,  

so on which sums  upto.
 

 
The number  of comparisons needed is at least   $\frac{3}{2}n$ 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$ 1will be applied on the first 2 $2$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
2*5--NOT POSSIBLE 
5*2--POSSIBLE (x[4][1]) 
x[9][0] = 9*4+ 0+1000 = 1036 
x[4][1]=4*4+1+1000=1017

$\frac{n}{}$

$Comparisons\; Req.\; for\; finding\; the\; Min\; Element..=\frac{n}{4}+\frac{n}{8}+\frac{n}{16}...=\frac{n}{2}$

$Total\; Number\; of\; Comparisons\; Number\; Required=n+\frac{n}{2}=\frac{3}{n}$