ITPEC FE Subject B April 2024 Question 12

Topic: String Processing

From the answer group below, select the correct answer to be inserted into blank in the program.

A string of character(s) is called a palindrome if it reads the same forwards and backwards. Here the input string consists of only the uppercase Roman alphabet. As an example, the string "MADAM" is a palindrome as it remains the same when written backwards (right to left). The procedure isPalindrome receives a string str as a parameter and outputs whether the string str is a palindrome or not. The procedure should use the minimum number of iterations for any number of characters in the string. Note that division is performed for data type integer, that is, a ÷ b is the quotient of a divided by b.

[Program]
○isPalindrome(string: str)
integer: i, j, len
boolean: flag
flag ← true
len ← number of characters in str
i ← 1
j ← len
while (blank)
if (the i-th character of string str ≠ the j-th character of string str)
flag ← false
exit the while block
endif
i ← i + 1
j ← j - 1
endwhile
if (flag)
output str, " is a palindrome."
else
output str, " is not a palindrome."
endif

Answer group

Explanation

i < (len ÷ 2) + 1 — the loop must compare each mirrored pair of characters exactly once, which takes len ÷ 2 passes.

i walks in from the left and j from the right, and each pass compares one mirrored pair. A string of len characters has len ÷ 2 such pairs (integer division); in an odd-length string the middle character pairs with itself and needs no check. So the loop must run for i = 1 to len ÷ 2, which is exactly the condition i < (len ÷ 2) + 1.

  • •"MADAM", length 5: 5 ÷ 2 = 2, so passes run at i = 1 (M, M) and i = 2 (A, A); the loop stops at the middle D
  • •"ABBA", length 4: 4 ÷ 2 = 2, so passes run at i = 1 (A, A) and i = 2 (B, B), and every pair is checked

Answer (b)

Why not others:

  • •(a) — i < j - 1 stops one pair early: in a 4-letter string the second test is 2 < 2, false, so positions 2 and 3 are never compared and "ABCA" is reported a palindrome
  • •(c) — i < (len ÷ 2) - 1 allows two passes fewer than needed: for 5 letters the first test is 1 < 1, so "MADAX" is reported a palindrome
  • •(d) — i < len ÷ j is false on the first test, since j equals len and the test is 1 < 1; no pair is compared and every string is reported a palindrome
  • •(e) — i < j ÷ 2 shrinks as j falls: for 5 letters the second test is 2 < 4 ÷ 2, false, so positions 2 and 4 are skipped and "ABCDA" is reported a palindrome

Key rule: A two-pointer palindrome check needs n ÷ 2 comparisons for n characters; test any loop bound on both an even and an odd length.

String Processing · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.