Programming Basics (Pseudocode Tracing)
The following function isPal returns true if the characters in the string array s read the same forward and backward (a palindrome). Array indices start at 1. What should replace 【a】 in the program?
○boolean: isPal(string array: s)
integer: n ← length(s)
for (i from 1 to n ÷ 2 step 1)
if (s[i] ≠ s[【a】])
return false
endif
endfor
return true- An − i + 1
- Bn − i
- Cn + i − 1
Show answer and explanation
Answer: A. n − i + 1
The i-th character is compared with the i-th character from the end. The 1st from the end is s[n] and the 2nd is s[n − 1], so the i-th from the end is s[n − i + 1]. Comparing the first half is enough: for n = 5, n ÷ 2 = 2.5, so i = 1 and 2 compare s[1] with s[5] and s[2] with s[4] (the middle s[3] need not be compared). With n − i the comparison is off by one, and even the palindrome "level" returns false, because s[1], "l", is compared with s[4], "e".
- A. Correct. It gives s[n] for i = 1 and s[n − 1] for i = 2: the i-th character from the end.
- B. This is off by one and compares with the (i + 1)-th character from the end. Even the palindrome "level" gives false.
- C. For i = 2 this is s[n + 1], beyond the end of the array.
Continue: 9 more Programming Basics (Pseudocode Tracing) questions