ITPEC FE Subject B October 2024 Question 16

Topic: String Processing

From the answer group below, select the correct combination of answers to be inserted into A through C in the program.

Function hammingDistance receives two strings as argument and returns Hamming distance as the return value. Hamming distance is a metric used to measure the difference between two strings of equal length. It counts the number of positions at which the corresponding characters are different. For instance, the return value is 2 when the function hammingDistance("101010", "111000") is called, because positions 2 and 5 have different characters.
It can also be extended to strings of different lengths by considering the unmatched characters as differences. For instance, the return value is 5 when the function hammingDistance("101010", "111000111") is called, because of two differences in first six characters and addition of three extra unmatched characters.

[Program]
○ integer: hammingDistance(string: s1, string: s2)
integer: distance, length1, length2, minLength, remainingLength
length1 ← length of s1
length2 ← length of s2
distance ← 0
minLength ← length1
if (A)
minLength ← length2
endif
for (increase i from 1 to minLength by 1)
if (the i-th character of string s1 B the i-th character of string s2)
distance ← distance + 1
endif
endfor
if (length1 > length2)
remainingLength = length1 - length2
else
remainingLength = length2 - length1
endif
distance ← C
return distance

Answer group

OptionABC

Explanation

A: length2 < length1, B: is not equal to, C: distance + remainingLength — compare up to the shorter length, count the positions that differ, then add the leftover characters.

  • •A: minLength starts as length1 and must be replaced by length2 only when length2 is smaller, so the loop never reads past the end of the shorter string.
  • •B: Hamming distance counts positions that differ, so distance goes up when the characters are not equal.
  • •C: every character of the longer string beyond minLength has no partner and counts as one difference; remainingLength is that count, added to the mismatches the loop found.

Check with hammingDistance("101010", "111000111"): minLength is 6, positions 2 and 5 differ so distance is 2, remainingLength is 3, and the result is 2 + 3 = 5, as the description says.

Answer (d)

Why not others:

  • •(e), (f), (g) and (h) — length2 > length1 sets minLength to the longer length; in the example the loop runs to 9 and reads characters 7 to 9 of "101010", which do not exist
  • •(a) and (b) — "is equal to" counts matching positions, 4 in the example; (b) returns 4 + 3 = 7, and (a) returns remainingLength alone, 3, discarding the loop's count
  • •(c) — distance + minLength adds the length of the overlap instead of the unmatched part: 2 + 6 = 8

Key rule: When comparing sequences of different lengths, loop only to the shorter length and handle the unmatched tail separately.

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.