Consider the following two C code segments. Y and X are one- and…
2015
Consider the following two C code segments. Y and X are one- and two-dimensional arrays of size n and n x n respectively, where 2 <= n <= 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 the same main memory page frame.
Code segment 1:
// initialize elements of Y to 0
// initialize elements of 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 of 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
- A.
Only S2 is correct
- B.
Only S3 is correct
- C.
Only S1 and S2 are correct
- D.
Only S1 and S3 are correct
Attempted by 26 students.
Show answer & explanation
Correct answer: C
Concept
A two-dimensional array in C is stored in row-major order: an entire row occupies consecutive memory locations, and the start of one row is exactly one row-width (n elements) past the start of the previous row. So scanning a fixed row (varying the column index) touches adjacent cells, whereas scanning a fixed column (varying the row index) jumps by a full row stride each step. Separately, the value stored at X[i][j] here is i+j, which is independent of how those cells are laid out in memory.
Application to each statement
S1 (final Y is the same): Segment 1 does Y[i] += X[0][i] = 0+i = i; segment 2 does Y[i] += X[i][0] = i+0 = i. Starting from Y all zeros, each segment leaves Y[i] = i for every index, so the final arrays are identical. S1 holds.
S2 (segment-1 accesses are contiguous): The loop reads X[0][0], X[0][1], ..., X[0][n-1] - all of row 0. Under row-major storage a full row is laid out in consecutive memory cells, so these accesses are adjacent. S2 holds.
S3 (segment-2 accesses are contiguous): The loop reads X[0][0], X[1][0], ..., X[n-1][0] - the first cell of each successive row. Consecutive rows are one row stride (n cells) apart, so these accesses are separated by n locations, not adjacent. Lying inside one page frame is about residency, not adjacency, so it does not make them contiguous. S3 fails.
Cross-check
Take n = 3 with the flat memory order X[0][0], X[0][1], X[0][2], X[1][0], X[1][1], X[1][2], X[2][0], X[2][1], X[2][2]. Segment 1 touches positions 0, 1, 2 (back-to-back). Segment 2 touches positions 0, 3, 6 (gaps of 3). Both produce Y = [0, 1, 2]. This confirms S1 true, S2 true, S3 false, so the statements that hold are exactly S1 and S2.