Arrays and Strings : MCQs & PYQs with Explanation

Option C

The array A[15][13] is stored in row-major order, which means elements are stored row by row. The formula to calculate the address of an element A[i][j] in row-major order is:
LOC(A[I][J])=BASE(A)+[I×N+J]×W
Where,

• BASE(A), represent base address of A.
• I, (Current row index), represent number of rows crossed to reach at particular row.
• J, (Current column index), represent elements crossed in particular row.
• N, represent total number of columns (number of elements in each row).
• W, represent word size or simply size (byte occupied by each element).

When the index starts from 0, the number of columns is specified in the array declaration. For example, in A[15][13], the total number of columns is 13.
So,
Base Address = 150
Number of Columns (N) = 13
Size of each element (W) = 2
Element to find = A[13][12] i.e., I = 13 and J = 12
LOC(A[13][12]) = 150+[13*13+12]*2
LOC(A[13][12]) = 150+[169+12]*2
LOC(A[13][12]) = 150+[181]*2
LOC(A[13][12]) = 150+362
LOC(A[13][12]) = 512

NOTE:

• In the absence of index bounds, always assume index starts from 0.
• Do not assume 1-based indexing unless the question specifically states: 'indices start from 1' or provides a declaration like A[1...4][1...5].

Option C

Arrays allow direct access to any element in constant time O(1) using its index, which is efficient because elements are stored at contiguous memory locations due to which they also benefit from locality of reference.

• Insertions and deletions in the middle are not efficient in arrays because elements must be shifted.
• Arrays store actual data, not references, so memory usage is not reduced in this way.
• Arrays are faster, not slower, in accessing elements due to direct indexing.

Option C

An array is a linear data structure in which elements are stored in contiguous memory locations. This layout allows for random access, meaning any element can be directly accessed using its index in constant time O(1).

Option A

To segregate positive and negative numbers in an array, we can scan the array only once and rearrange elements using a two-pointer or partition-based approach. In two pointers approach, one at the beginning (left) and one at the end (right) of the array.
The left pointer moves from the beginning towards the right, looking for a positive number. The right pointer moves from the end towards the left, looking for a negative number.
When the left pointer finds a positive number and the right pointer finds a negative number, they are swapped.
If left points to a negative number, or right points to a positive number, the respective pointers are adjusted accordingly (i.e., increment left or decrement right).
Even in the worst case, each element is examined only once, which is why the overall time complexity of the algorithm is O(n).

#include<stdio.h>
void main()
{
    int arr[5]={-3,5,-10,-7,9},i;
    int left=0;
    int right=4;
    printf("Array Before Segregated");
    for(i=0;i<5;i++)
        printf("%d	",arr[i]);
    while (left<right)
    {
        // Move left if the current element is negative
        while(arr[left]<0 && left<right)
            left++;
        // Move right if the current element is positive
        while(arr[right]>0 && left<right)
            right--;
        // Swap if left is positive and right is negative
        if (left<right)
        {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    printf("Array After Segregated");
    for(i=0;i<5;i++)
        printf("%d	",arr[i]);
}
OUTPUT
Array Before Segregated
-3	5	-10	-7	9	
Array After Segregated
-3	-7	-10	5	9

Option B

An Array is a linear data structure that holds multiple elements of the same data type (homogeneous) in contiguous memory locations. This allows easy and efficient access to elements using their index. The index of an array usually starts from 0.

Option B

In column-major implementation, address of an element A[I][J] is calculated using the formula below:

1. WHEN INDEX STARTS FROM 0:
   • LOC(A[I][J])=BASE(A)+[J ×M+I]W
2. WHEN INDEX DOES NOT STARTS FROM 0 / CUSTOM INDEX:
   • LOC(A[I][J])=BASE(A)+[(J-L2)×M+(I-L1)]W

Where,

• BASE(A), represent base address of A.
• I, (Current row index), represent elements crossed in particular column.
• J, (Current column index), represent number of columns crossed to reach at particular column.
• M, represent total number of row (number of elements in each column).
  • When the index starts from 0, the number of rows is specified in the array declaration. For example, in A[3][4], the total number of rows is 3.
  • In custom index (other than 0) value of M is calculated as: U1-L1+1
• L1 is the lower bound of row.
• L2 is lower bound of column.
• U1 is upper bound of row.
• U2 is upper bound of column.
• W, represent word size or simply size (byte occupied by each element).

Here the array is defined as A[-8…2][-12…-2]. So, we calculate the memory location using the custom index formula.
LOC(A[I][J])=BASE(A)+[(J-L2)×M+(I-L1)]W
Find location of A[0][-4]= ?
Given,
BASE (A) = 5894
W = 4 Bytes
L1 = -8
L2 = -12
U1 = 2
I = 0
J = -4
M = U1-L1 = 2-(-8)+1 = 11
LOC(A[0][-4]) = 5894+[(-4-(-12))*11+(0-(-8))]*4
LOC(A[0][-4]) = 5894+[8*11+8]*4
LOC(A[0][-4]) = 5894+[88+8]*4
LOC(A[0][-4]) = 5894+96*4
LOC(A[0][-4]) = 5894+384
LOC(A[0][-4]) = 6278

Option D

Arrays provide several advantages in programming. They offer an easy and organized way to store elements of the same data type, allow convenient representation of matrices using 2-D arrays, and are commonly used to implement other data structures such as stacks and queues.

Option B

The Upper Bound of an array refers to the largest valid index that can be accessed in the array. If an array has n elements and uses zero-based indexing, the lower bound is 0 and upper bound is n−1.

• Length refers to the total number of elements.
• Capacity refers to the maximum number of elements the array can hold.

Option C

Spatial Locality is a principle of memory access that states if a memory location is accessed, nearby memory locations are likely to be accessed soon. Since arrays store data in contiguous memory locations, accessing elements sequentially benefits heavily from spatial locality. Thus, arrays highly utilize this concept.

Option B

Array A stores number of cars sold each year starting from 1932 So, A[0] corresponds to year 1932 or lower bound of array is 1932.
Base address = 200
Each element occupies 4 words i.e., 4 Bytes.
We are asked to find the address of the element corresponding to year 1965 or find the address of index position 1965. So,
LOC (A[I])=Base(A) + (I-Lower Bound) * W
LOC (A[1965]) = 200 + (1965-1932)*4
LOC (A[1965]) = 200 + 33 * 4
LOC (A[1965]) = 200 + 132
LOC (A[1965]) = 332

Option D

An array is a linear data structure that stores a collection of similar data elements in contiguous memory locations. 
One of the most important features of arrays is random access, which means any element can be accessed directly using its index like arr[i] without traversing other elements.

Option C

A subarray is a contiguous part of an array. For an array of size n, the subarrays can range in size from 1 element up to n elements.
Suppose an array of 5 elements is as:
int arr[5]={11,22,33,44,55};

• The number of subarrays of size 1 is n (each individual element).

arr1[1]={11};
arr2[1]={22};
arr3[1]={33};
arr4[1]={44};
arr5[1]={55};

• The number of subarrays of size 2 is n−1 (pairwise combinations of consecutive elements).

arr6[2]={11,22};
arr7[2]={22,33};
arr8[2]={33,44};
arr9[2]={44,55};
Remember, its array so consecutive sequence is required.

• The number of subarrays of size 3 is n−2.

arr10[3]={11,22,33};
arr11[3]={22,33,44};
arr12[3]={33,44,55};

• The number of subarrays of size 4 is n−3.

arr13[4]={11,22,33,44};
arr14[4]={22,33,44,55};

• The number of subarrays of size 5 is n−4.

arr15[5]={11,22,33,44,55}; and so on.

If the size of the array is n = 5, then the total number of possible subarrays can be calculated as follows.
From the first element, we can form 5 subarrays, from the second element 4 subarrays, from the third element 3 subarrays, from the fourth element 2 subarrays, and from the last element 1 subarray.

So, the total number of subarrays is:
5+4+3+2+1 = 15

In general, for an array of size n, the total number of subarrays is:
n+(n−1)+(n−2)+ …+1

This is the sum of the first n natural numbers, which forms an arithmetic series. The sum of this series is given by the formula: n*(n+1)/2.
Therefore, an array of size n has exactly n(n+1)/2 subarrays.
 

Option D

A subarray is a contiguous part of an array, meaning the elements must be taken in order and without skipping any element in between.
For the array arr[] = {1,2,3}, the possible subarrays are {1}, {2}, {3}, {1,2}, {2,3}, and {1,2,3}. All these subarrays maintain the original order and continuity of elements.

• {3,1} is invalid because it is not contiguous and changes the order.
• {2,3,1} is invalid because subarrays cannot wrap around the array.
• {1,3} is invalid because it skips the element 2, so it is not contiguous.

Option B

In row-major order, elements of a 2-D array are stored row by row in memory. This means the elements in the first row are stored first, followed by the second row, and so on.

(1) C uses row-major storage → rows stored one after another in memory.
(2) Fortran, MATLAB, R use column-major → columns stored one after another.

Option B

The function max() is defined as finding an element that is greater than its left and right neighbors (if they exist). To ensure that such an element is found in the worst case, the algorithm may need to check every element of the array.
In the worst scenario, the required element could be at the end of the array or may not exist until the last comparison. Since each element is checked at most once, the total number of comparisons grows linearly with n.
Therefore, the worst-case time complexity of the function max() on an array of size n is O(n).