Array Concepts MCQs & GATE PYQs - Data Structure [ GATE CSE ]

Master Array for your Data Structure course and the GATE exam. This guide covers key concepts, essential MCQs, and previous year questions (PYQs) to sharpen your skills in Array.

Array Concepts, tricks , Tips

Array basics: contiguous memory, indexing starts at 0 in C/C++/Java, row-major layout for 2D arrays in C, typical boundary checks, pitfalls with off-by-one errors.

• 2D arrays: element address = base + ((i * numCols) + j) * elementSize (row-major)
• SIP tricks: practice binary search, two-pointer, and prefix-sum problems on arrays.

Array Practice MCQs & GATE PYQs

1. An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i+1..n] is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A? [ GATE CSE 2025 SET-2 ]

Answer & Explanation

Correct Answer: D) Θ(log n)

A bitonic array increases to a single peak and then decreases. We can find an element using a modified binary-search based approach, giving logarithmic time complexity.

1. Find the Peak: Find the maximum (peak) in Θ(log n) by comparing A[mid] and A[mid + 1].
2. Binary Search Two Sides: After the peak, perform binary search on the increasing side and binary search (on reversed order) on the decreasing side.

The overall worst-case cost is still Θ(log n).

Trick to Remember

Think of a bitonic array as two sorted sequences joined at a peak — peak finder + binary searches => logarithmic complexity.

2. 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 _____ [ GATE CSE 2024 SET-2 ]

Answer & Explanation

Correct Answer: 3

The "distance" is the minimum number of replacements needed to make the array sorted (non-decreasing).

This problem is a classic application of the Longest Non-Decreasing Subsequence (LIS).

• The elements that form the LIS are already in the correct relative order, so we can **keep** them.
• The elements that are *not* part of the LIS must be **replaced** to fit into the sorted sequence.

Therefore, the formula is:
Distance = (Total Array Length) - (Length of LIS)

---

1. Find the LIS for A = [2, 5, 3, 1, 4, 2, 6]:

We are looking for the longest subsequence where each element is greater than or equal to the previous one.

Let's trace one such subsequence: with the LIS [2,3,4,6] highlighted]

• Start with 2 (at index 0)
• Next is 3 (at index 2)
• Next is 4 (at index 4)
• Next is 6 (at index 6)

One LIS is [2, 3, 4, 6]. The length of this subsequence is 4. (Note: Other subsequences like [2, 2, 6] or [1, 4, 6] exist, but none are longer than 4).

2. Calculate the Distance:

• Total Array Length = 7
• Length of LIS = 4
• Distance = 7 - 4 = 3

This means we must replace 3 elements (namely 5, 1, and the second 2) to make the entire array sorted. For example, [2, 2, 3, 3, 4, 4, 6].

Trick to Remember

When a question asks for the "minimum number of changes/replacements/removals" to make a sequence sorted, it's almost always a variation of the Longest Increasing (or Non-Decreasing) Subsequence (LIS) problem.

The number of items to keep is the LIS.
The number of items to change/remove is (Total Length - LIS).

3. What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n? [ GATE CSE 2021 SET-2 ]

Answer & Explanation

Correct Answer: B) Θ(log₂(n))

This problem can be analyzed using a recurrence relation. Let T(n) be the number of operations for an array of size n.

1. Divide: In each step, binary search calculates the middle index, (e.g., `mid = (low + high) / 2`). This involves a constant number of arithmetic operations (one addition, one division). This is Θ(1) work.
2. Conquer: After the comparison, the algorithm makes a recursive call on *only one* of the subarrays (either the left or the right half).
3. Recurrence Relation: In the worst case (when the element is not found), the problem of size `n` is reduced to a problem of size `n/2` plus the constant work to find the middle. This gives the relation:
   T(n) = T(n/2) + Θ(1)

Solving this recurrence relation (using the Master Theorem or by substitution) shows that the algorithm performs Θ(1) work at each level of recursion, and the depth of the recursion is log₂(n).

Therefore, the total number of arithmetic operations in the worst case is the sum of the constant operations at each level, which is Θ(1) * log₂(n) = Θ(log₂(n)).

Trick to Remember

Binary search is the classic "divide-and-conquer" algorithm where you **throw away half** the problem at each step. Any algorithm that repeatedly cuts the problem size in half will have a logarithmic (log n) time complexity.

4. 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? [ GATE CSE 2021 SET-1 ]

Answer & Explanation

Correct Answer: C) t > n and t ≤ 3⌈n/2⌉

The question asks for the tightest possible worst-case bound (the "lowest upper bound") to find both the minimum and maximum element. Let's call this optimal number of comparisons $t$.

1. What is the value of $t$?

A naive approach (finding min, then finding max) takes $(n-1) + (n-1) = 2n-2$ comparisons. However, we can do better.

The optimal algorithm (often called the "compare in pairs" method) works as follows:

• Process elements in pairs. For each pair $(a, b)$, compare them (1 comparison).
• Compare the smaller of the pair with the current `min` (1 comparison).
• Compare the larger of the pair with the current `max` (1 comparison).

This method (with careful handling for odd/even $n$) establishes that the lowest upper bound is exactly: $$t = \lceil \frac{3n}{2} \rceil - 2$$

2. Analyzing Option C: $t > n$ and $t \le 3\lceil n/2 \rceil$

Let's check both parts of this statement using our formula for $t$.

Part 1: Is $t \le 3\lceil n/2 \rceil$? (Checking the upper bound)

• If $n$ is even ($n=2k$):
  $t = \lceil 3(2k)/2 \rceil - 2 = 3k - 2$.
  The expression $3\lceil n/2 \rceil$ becomes $3\lceil 2k/2 \rceil = 3k$. Is $3k - 2 \le 3k$? Yes, this is true.
• If $n$ is odd ($n=2k+1$):
  $t = \lceil 3(2k+1)/2 \rceil - 2 = \lceil 3k + 1.5 \rceil - 2 = (3k+2) - 2 = 3k$.
  The expression $3\lceil n/2 \rceil$ becomes $3\lceil (2k+1)/2 \rceil = 3(k+1) = 3k+3$. Is $3k \le 3k+3$? Yes, this is true.

So, the second part $t \le 3\lceil n/2 \rceil$ is correct for all $n \ge 1$.

Part 2: Is $t > n$? (Checking the lower bound)

• We are checking if $\lceil 3n/2 \rceil - 2 > n$.
• This simplifies to $\lceil 3n/2 - n \rceil - 2 > 0$, which is $\lceil n/2 \rceil - 2 > 0$, or $\lceil n/2 \rceil > 2$.
• Let's test small values:
  • $n=1$: $\lceil 1/2 \rceil = 1$. (1 ≯ 2, False)
  • $n=2$: $\lceil 2/2 \rceil = 1$. (1 ≯ 2, False)
  • $n=3$: $\lceil 3/2 \rceil = 2$. (2 ≯ 2, False)
  • $n=4$: $\lceil 4/2 \rceil = 2$. (2 ≯ 2, False)
  • $n=5$: $\lceil 5/2 \rceil = 3$. (3 > 2, True)

The first part $t > n$ is true for all $n \ge 5$. In algorithm analysis, statements are often considered "correct" if they are asymptotically true (true for all sufficiently large $n$).

Conclusion:
Option C is the only choice that is asymptotically correct. The other options are asymptotically false (e.g., Option D fails because $t \approx 1.5n$, which is not $\le n$; Option A fails because $t \approx 1.5n$, which is not $> 2n-2$).

Trick to Remember

Finding min and max together is a classic problem. The tight bound is $\lceil 3n/2 \rceil - 2$, which is $\Theta(n)$. You just need to find the option that correctly "brackets" this $1.5n$ behavior.

• $t > n$: True (since $1.5n > n$)
• $t \le 3\lceil n/2 \rceil$: True (since $1.5n$ is roughly $\le 1.5n$)

The other options make asymptotically false claims, like $t > 2n$ or $t \le n$.

5. 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? [ ISRO CSE 2020 ]

Answer & Explanation

Correct Answer: B) 4, 7, 10, 23, 67, 12, 5

Insertion sort works by building a sorted subarray at the beginning of the list. In each "pass," it takes the next unsorted element and inserts it into its correct position within the already sorted subarray.

Initial Array: [10, 4, 7, 23, 67, 12, 5]

---

Pass 1:

• Element to insert: 4 (from index 1)
• Sorted subarray: [10]
• Action: Compare 4 with 10. Since 4 < 10, shift 10 right and insert 4.
• Array after Pass 1: [4, 10, 7, 23, 67, 12, 5]

Pass 2:

• Element to insert: 7 (from index 2)
• Sorted subarray: [4, 10]
• Action: Compare 7 with 10. Since 7 < 10, shift 10 right. Compare 7 with 4. Since 7 > 4, insert 7.
• Array after Pass 2: [4, 7, 10, 23, 67, 12, 5]

Pass 3:

• Element to insert: 23 (from index 3)
• Sorted subarray: [4, 7, 10]
• Action: Compare 23 with 10. Since 23 > 10, the element is already in its correct sorted position relative to the subarray. No shifts are needed.
• Array after Pass 3: [4, 7, 10, 23, 67, 12, 5]

Trick to Remember

A "pass" in insertion sort typically refers to picking one element from the unsorted part and "inserting" it into the sorted part. After $k$ passes, the first $k+1$ elements of the array will be sorted *relative to each other*.

After 3 passes, the first 4 elements (at indices 0, 1, 2, 3) must be sorted. Only option B satisfies this (4, 7, 10, 23).