Arrays - Practice MCQs for CCAT

Correct Answer: B - O(1)

Arrays provide constant time O(1) access because elements are stored in contiguous memory locations.

Correct Answer: A - O(n)

Inserting at beginning requires shifting all elements, making it O(n).

Correct Answer: A - n-1

Arrays are 0-indexed, so last element is at index n-1.

Correct Answer: C - Quick Sort

Quick Sort has O(n²) worst case (already sorted) but O(n log n) average case.

Correct Answer: D - m × n

A 2D array of m rows and n columns has m × n total elements.

Correct Answer: C - Sorted array only

Binary search requires the array to be sorted to work correctly.

Correct Answer: C - O(log n)

Binary search halves the search space each time, giving O(log n).

Correct Answer: B - O(n)

An array of n elements uses O(n) space.

Correct Answer: D - Dynamic size

Arrays have fixed size. Dynamic size is not an advantage of static arrays.

Correct Answer: B - B + i × S

Address of arr[i] = Base + i × Size of each element.

Correct Answer: C - O(n)

Linear search checks each element one by one, taking O(n) in worst case.

Correct Answer: A - Sorted

Binary search only works on sorted arrays as it relies on the ordering to eliminate half the elements.

Correct Answer: B - O(log n)

Binary search halves the search space each time, giving O(log n) complexity.

Correct Answer: D - m × n

A 2D array with m rows and n columns has m × n total elements.

Correct Answer: C - Row by row

In row-major order, elements of each row are stored contiguously in memory.

Correct Answer: A - Array with mostly zero/default values

A sparse array has most of its elements as zero or default values.

Correct Answer: D - O(n)

All remaining n-1 elements must be shifted left, taking O(n) time.

Correct Answer: D - Rows can have different sizes

Jagged arrays (arrays of arrays) can have rows of different lengths.

Correct Answer: C - Doubling capacity

Most dynamic array implementations double capacity when full for amortized O(1) insertion.

Correct Answer: D - O(n)

Must check every element to find minimum, taking O(n) time.

Correct Answer: B - O(1)

Array elements are stored in contiguous memory locations, so accessing any element by index requires a single base address + offset calculation, giving O(1) time complexity.

Correct Answer: B - O(n)

Inserting at the beginning requires shifting all n existing elements one position to the right, resulting in O(n) time complexity.

Correct Answer: B - O(log n)

Binary search repeatedly halves the search space by comparing with the middle element. This halving leads to O(log n) comparisons in the worst case.

Correct Answer: B - O(n)

After deleting the element, all subsequent elements must be shifted one position to the left to fill the gap, resulting in O(n) time in the worst case.

Correct Answer: D - Easy insertion and deletion at any position

Insertion and deletion at arbitrary positions in arrays require shifting elements, making them O(n) operations. This is a disadvantage, not an advantage of arrays.

Correct Answer: C - 2028

Address = Base + (index × size) = 2000 + (7 × 4) = 2000 + 28 = 2028.

Correct Answer: A - O(n)

In the worst case, the element is at the last position or not present, requiring comparison with all n elements, giving O(n) time complexity.

Correct Answer: C - Base + (i × N + j) × size

In row-major order, elements of each row are stored contiguously. To reach A[i][j], we skip i complete rows (each of N elements) and then j elements within the current row.

Correct Answer: B - O(n)

Every element must be checked to determine the maximum in an unsorted array, requiring a single pass through all n elements, giving O(n).

Correct Answer: A - Search using binary search

Binary search on a sorted array achieves O(log n) by halving the search space at each step. Insertion and deletion still require shifting elements (O(n)), and traversal is always O(n).

Correct Answer: D - Undefined behavior

C does not perform bounds checking on arrays. Accessing an out-of-bounds index leads to undefined behavior — it may read garbage values, crash, or produce unpredictable results.

Correct Answer: D - Column by column

In column-major order (used by languages like Fortran), all elements of the first column are stored first, then all elements of the second column, and so on.

Correct Answer: A - O(n)

An array of n elements requires memory proportional to n to store all elements, giving O(n) space complexity.

Correct Answer: A - Insertion sort

Insertion sort performs very well on nearly sorted arrays with O(n) best-case time complexity, as very few shifts are needed when elements are almost in order.

Correct Answer: C - O(m + n)

Using the two-pointer technique, we compare elements from both arrays and place the smaller one in the result. Each element is processed exactly once, giving O(m + n).

Correct Answer: D - Triplet representation (row, col, value)

A sparse matrix has mostly zero elements. Storing only non-zero elements as (row, col, value) triplets uses far less memory than a full 2D array that stores all zeros.

Correct Answer: B - Element not found

Binary search requires the target element to be present in the array. Since 7 is not in [2, 4, 6, 8, 10, 12], the search returns 'element not found'.

Correct Answer: A - Random access by index

Arrays provide O(1) random access by index due to contiguous memory allocation. Linked lists require O(n) traversal for the same operation.

Correct Answer: C - 11

Binary search needs at most ⌊log₂(n)⌋ + 1 comparisons. For n = 1024: log₂(1024) = 10, so maximum comparisons = 10 + 1 = 11.

Correct Answer: B - O(n)

Reversing in-place requires swapping elements from both ends toward the center, performing n/2 swaps. Since O(n/2) simplifies to O(n), the time complexity is O(n).

Correct Answer: A - Each row can have a different number of columns

A jagged array allows each row to have a different length, unlike a standard 2D array where all rows must have the same number of columns.

Correct Answer: A - O(n²)

The brute force approach compares every pair of elements using two nested loops, resulting in n(n-1)/2 comparisons, which is O(n²).

Correct Answer: B - A new larger array is allocated and elements are copied

Dynamic arrays allocate a new array (typically double the size), copy all existing elements to the new array, and then add the new element. This is called resizing or growing.

Correct Answer: A - O(1)

Although occasional resizing takes O(n), it happens infrequently. When averaged over a sequence of n insertions, each insertion costs O(1) amortized time due to the doubling strategy.

Correct Answer: D - 1

The second largest element can be found in a single pass by maintaining two variables: one for the largest and one for the second largest, updating them as we traverse.

Correct Answer: C - O(n)

With the optimization of a flag to detect if no swaps occurred in a pass, bubble sort completes in one pass (O(n)) on an already sorted array.

Correct Answer: B - Index = i(i+1)/2 + j

In a lower triangular matrix, elements are stored row-wise. Before row i, there are 1+2+...+i = i(i+1)/2 elements. Adding j gives the position of A[i][j].

Correct Answer: A - O(n)

The Dutch National Flag algorithm uses three pointers (low, mid, high) and sorts the array in a single pass through all elements, giving O(n) time complexity.

Correct Answer: C - O(log log n)

For uniformly distributed data, interpolation search estimates the position of the target using linear interpolation, achieving O(log log n) average time complexity.

Correct Answer: D - O(n)

The reversal algorithm rotates an array by reversing three subarrays: first k elements, remaining n-k elements, and then the entire array. Each reversal is O(n), giving O(n) overall.