IPA FE Subject B first sample Question 5

Topic: String Processing

A question IPA Japan published in 基本情報技術者試験 科目Bのサンプル問題 問5, translated into English. ITPEC is based on the same exams.

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

This is a program that, for any two different characters c1 and c2, calculates the ratio at which c2 appears immediately after c1 in the English words contained in a group of English words. English words consist of lowercase English letters only. When the last character of an English word is c1, that position is not included in the calculation of the ratio. For example, in the group of English words consisting of the four English words “importance,” “inflation,” “information,” and “innovation” shown in the figure, let c1 be “n” and c2 be “f”. Other than the last characters of the English words, there are five “n”s, and of these, two have “f” as the next character. Therefore, the ratio to be calculated is 2 ÷ 5 = 0.4. When the sequence of c1 and c2 never appears, the ratio is defined as 0 regardless of the number of occurrences of c1.

importanceThe nextcharacter is “c”inflationThe nextcharacter is “f”informationThe nextcharacter is “f”innovationThe nextcharacter is “n”The nextcharacter is “o”Not included inthe calculationof the ratio

Figure Example of a group of English words consisting of four words

In the program, the group of English words is stored in the Words-type global variable words. The table shows an explanation of the methods of the class Words. In this question, the operator “+” for strings represents the concatenation of strings. Also, the operator “÷” for integers performs the calculation as real numbers.

Table Explanation of the methods of the class Words

MethodReturn valueDescription
freq(string: str)integerReturns the number of occurrences of the string str in the group of English words.
freqE(string: str)integerReturns the number of English words that end with the string str in the group of English words.
[Program]
global: Words: words /* stores the group of English words */
/* returns the ratio at which c2 appears immediately after c1 */
○ real: prob(character: c1, character: c2)
string: s1 ← a string consisting only of the one character c1
string: s2 ← a string consisting only of the one character c2
if (words.freq(s1 + s2) is greater than 0)
return blank
else
return 0
endif

Answer group

Explanation

words.freq(s1 + s2) ÷ (words.freq(s1) - words.freqE(s1)) — the ratio is the number of “c1 then c2” pairs over the number of c1s that have a next character.

The numerator counts the places where c2 follows c1. Each is one occurrence of the two-character string s1 + s2, so it is words.freq(s1 + s2).

The denominator counts the c1s that are not the last character of a word. words.freq(s1) counts every c1; since s1 is one character, a word can end with it at most once, so words.freqE(s1) is exactly the number of c1s to leave out. The denominator is words.freq(s1) - words.freqE(s1).

Check with the figure: freq("nf") is 2, freq("n") is 8 (1 + 2 + 2 + 3) and freqE("n") is 3, so 2 ÷ (8 − 3) = 0.4, as the description says. The if returns 0 when the pair never appears; when it does appear, at least one c1 has a next character, so the denominator is never 0.

Answer (c)

Why not others:

  • •(a) — the ratio upside down: 5 ÷ 2 = 2.5 for the example, more than 1
  • •(b) — upside down and built on c2 instead of c1: freq("f") is 2 and freqE("f") is 0, giving 2 ÷ 2 = 1
  • •(d) — divides by the occurrences of c2, not of c1: 2 ÷ 2 = 1 for the example, though only two of the five “n”s are followed by “f”

Key rule: For how often B follows A, divide the count of the pair AB by the count of A's that have a successor, so subtract the A's that end a word.

String Processing · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.