GATE CS 2015 Set 3 Q.40 (CS Q.30): Pointers, Arrays and Strings

Consider the following two C code segments. $Y$ and $X$ are one and two dimensional arrays of size $n$ and $n \times n$ respectively, where $2 \le n \le 10$ . Assume that in both code segments, elements of $Y$ are initialized to 0 and each element $X[i][j]$ of array $X$ is initialized to $i + j$ . Further assume that when stored in main memory all elements of $X$ are in same main memory page frame.

Code Segment 1:

// initialize elements of Y to 0
// initialize elements X[i][j] of X to i + j
for (i = 0; i < n; i++)
    Y[i] += X[0][i];

Code Segment 2:

// initialize elements of Y to 0
// initialize elements X[i][j] of X to i + j
for (i = 0; i < n; i++)
    Y[i] += X[i][0];

Which of the following statements is/are correct?
S1: Final contents of array $Y$ will be same in both code segments
S2: Elements of array $X$ accessed inside the for loop shown in code segment 1 are contiguous in main memory
S3: Elements of array $X$ accessed inside the for loop shown in code segment 2 are contiguous in main memory

Only S2 is correct

Only S3 is correct

Only S1 and S2 are correct

Only S1 and S3 are correct

Official answer and solution

Official answer: C
From: Official GATE 2015 answer key

Solution

Trace array values and memory layout in C (row-major order).

Evaluate Statement S1:

In both segments, $X[i][j] = i + j$ .
Code Segment 1 accesses $X[0][i] = 0 + i = i$ . So $Y[i] += i$ , giving $Y[i] = i$ .
Code Segment 2 accesses $X[i][0] = i + 0 = i$ . So $Y[i] += i$ , giving $Y[i] = i$ .
Since $Y[i] = i$ for all $0 \le i < n$ in both cases, the final contents of array $Y$ are identical. Statement S1 is correct.

Evaluate Statement S2:

In C, two-dimensional arrays are stored in row-major order: row 0 elements ( $X[0][0], X[0][1], \dots, X[0][n-1]$ ) occupy consecutive contiguous memory addresses.
Code Segment 1 accesses $X[0][i]$ for $i = 0, 1, \dots, n - 1$ , which are adjacent elements in row 0.
Therefore, the elements accessed are contiguous in memory. Statement S2 is correct.

Evaluate Statement S3:

Code Segment 2 accesses $X[i][0]$ for $i = 0, 1, \dots, n - 1$ , which are the first elements of successive rows.
In row-major layout, $X[i+1][0]$ is located $n$ elements after $X[i][0]$ . These are not contiguous in memory (they have stride $n$ ). Statement S3 is incorrect.

Thus, only Statements S1 and S2 are correct (Option C).

Final answer

Common trap

Confusing row-major and column-major memory ordering, thinking that accessing along columns (X[i][0]) is contiguous.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 40 of 65, printed as CS Q.30
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source