Programming Basics (Pseudocode Tracing)
The following procedure bubble is a bubble sort that sorts the integer array data in ascending order. swap(data, j, k) is a procedure that swaps the values of data[j] and data[k]. Array indices start at 1. What should replace 【a】 in the program?
○bubble(integer array: data)
integer: n ← length(data)
for (i from n down to 2 step 1)
for (j from 1 to 【a】 step 1)
if (data[j] > data[j + 1])
swap(data, j, j + 1)
endif
endfor
endfor- Ai
- Bn − i
- Ci − 1
Show answer and explanation
Answer: C. i − 1
The outer i is the position to which each pass moves the largest remaining value (n, n − 1, …, 2 from the end). The inner loop compares data[j] with data[j + 1], so a final value of i − 1 for j compares adjacent pairs up to data[i] without going beyond the array. The first pass, with i = n, moves the largest value to data[n]; the next goes up to data[n − 1], and so on, narrowing the range by one each time. With i in 【a】, the first pass would read data[n + 1].
- A. For i = n, j reaches n and data[n + 1] is read, beyond the end of the array.
- B. For i = n the final value of j is 0 and nothing is compared; the ranges are reversed and the data is not sorted. {5, 3, 8, 1, 4} becomes {3, 5, 1, 8, 4}.
- C. Correct. Adjacent pairs up to data[i] are compared, moving the largest value to data[i].
Continue: 9 more Programming Basics (Pseudocode Tracing) questions