今週の午後問題〔問題〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/this_weeks_exercise_h29a_algorithm_cover-640x360.jpg)
error
この記事は基本情報技術者試験の旧制度( 2022 年以前)の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。
このコーナーでは毎週月曜に午後の必須選択問題から 1 問ピックアップして出題し、 解答欄 を設け、読者の皆さまも参加して解答できます! その週の金曜にはその解答と 矢沢久雄 さんによる 解説 ページを公開し、皆さんの正解率も発表します。
今回が「アルゴリズム特集」、最後の出題です!また今週の午後問も受験締切が近づいたので、一旦、お休みします。
最後を飾るのは 「 2017 年度 秋期 文字列の誤りの検出」です。
ぜひ腕試しにお使い下さい!
今週の午後問題
2017 年度 秋期 アルゴリズム 文字列の誤りの検出
問 1
次のプログラムの説明及びプログラムを読んで,設問 1 ~ 4 に答えよ。
文字 | ␣ | . | , | ? | a | b | c | d | e | f | g | h | i | j | k |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
文字 | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
数値 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
〔プログラムの説明〕
検査文字の生成と検査文字付文字列の検証の手順を示す。
- 検査文字の生成
- 文字列の末尾の文字を 1 番目の文字とし,文字列の先頭に向かって奇数番目の文字に割り当てた数値を 2 倍して N で割り,商と余りの和を求め,全て足し合わせる。
- 偶数番目の文字に割り当てた数値は,そのまま全て足し合わせる。
- 01 と 02 の結果を足し合わせる。
- N から 03 で求めた総和を N で割った余りを引く。さらにその結果を, N で割り,余りを求める。求めた数値に対応する文字を検査文字とする。
- 検査文字付文字列の検証
- 検査文字付文字列の末尾の文字を 1 番目の文字とし,文字列の先頭に向かって偶数番目の文字に割り当てた数値を 2 倍して N で割り,商と余りの和を求め,全て足し合わせる。
- 奇数番目の文字に割り当てた数値は,そのまま全て足し合わせる。
- 01 と 02 の結果を足し合わせる。
- 03 で求めた総和が N で割り切れる場合は,検査文字付文字列に誤りがないと判定する。 N で割り切れない場合は,検査文字付文字列に誤りがあると判定する。
〔検査文字付文字列の生成例〕
表 1 及び検査文字の生成の手順を用いることによって,文字列 ipa␣␣ に対し,生成される検査文字は f である。
検査文字付文字列は,文字列の末尾に検査文字を追加し, ipa␣␣f となる。
〔プログラムの仕様〕
各関数の仕様を 1. ~ 4.に示す。ここで,配列の添字は 1 から始まるものとする。
- 関数 calcCheckCharacter は,文字列及び文字列長を用いて生成した検査文字を返す。関数 calcCheckCharacter の引数及び返却値の仕様は,表 2 のとおりである。
表 2 関数 calcCheckCharacter の引数及び返却値の仕様 引数/返却値 データ型 入力/出力 説明 input[] 文字型 入力 文字列が格納されている 1 次元配列 len 整数型 入力 文字列の文字列長( 1 以上) 返却値 文字型 出力 生成した検査文字を返す。 関数 calcCheckCharacter は,関数 getValue, 関数 getChar を使用する。
- 関数 validateCheckCharacter は,検査文字付文字列を検証し,検証結果を返す。関数 validateCheckCharacter の引数及び返却値の仕様は,表 3 のとおりである。
表 3 関数 validateCheckCharacter の引数及び返却値の仕様 引数/返却値 データ型 入力/出力 説明 input[] 文字型 入力 検査文字付文字列が格納されている 1 次元配列 len 整数型 入力 検査文字付文字列の文字列長 ( 2 以上) 返却値 論理型 出力 検査文字付文字列に誤りがないと判定した場合は true ,
誤りがあると判定した場合は false を返す。関数 validateCheckCharacter は,関数 getValue を使用する。
- 関数 getValue は,表 1 に従い,引数として与えられた文字に割り当てた数値を返す。
- 関数 getChar は,表 1 に従い,引数として与えられた数値に対応する文字を返す。
設問 1
プログラム中のに入れる正しい答えを,解答群の中から選べ。ここで, a1 と a2 に入れる答えは, a に関する解答群の中から組合せとして正しいものを選ぶものとする。
○文字型関数 : calcCheckCharacter(文字型: input[], 整数型: len) ○整数型: N, sum, i, value, check_value ○論理型: is_even ・ N ← 30 ・ sum ← 0 ・ is_even ← false ■ i: len, i > 0, -1 | ・ value ← getValue(input[i]) | ▲ is_even = a1 | | ・ sum ← sum + value |-+--- | | sum ← sum + (value × 2) ÷ N + (value × 2) % N | ▼ | ・ is_even ← not is_even ■ ・ check_value ← b ・ return getChar(check_value)
○論理型関数: validateCheckCharacter(文字型: input[], 整数型: len) ○整数型: N, sum, i, value ○論理型: is_odd, ret_value ・ N ← 30 ・ sum ← 0 ・ is_odd ← true ・ ret_value ← true ■ i: len, i > 0, -1 | ・ value ← getValue(input[i]) | ▲ is_odd = a2 | | ・ sum ← sum + value |-+--- | | ・ sum ← sum + (value × 2) ÷ N + (value × 2) % N | ▼ | ・ is_odd ← not is_odd ■ ▲ c | ・ ret_value ← false ▼ return ret_value
a に関する解答群
al | a2 | |
---|---|---|
ア | false | false |
イ | false | true |
ウ | true | false |
エ | true | true |
b に関する解答群
ア N – sum % N
イ sum % N
ウ (N – sum % N) % N
エ (sum – N) % N
c に関する解答群
ア sum ÷ N = 0
イ sum ÷ N ≠ 0
ウ sum % N = 0
エ sum % N ≠ 0
設問 2
次の記述中のに入れる正しい答えを,解答群の中から選べ。
ケース | 検査文字付文字列 |
---|---|
1 | ipb␣␣f |
2 | api␣␣f |
3 | pia␣␣f |
4 | ␣␣apif |
d に関する解答群
ア 1 と 2 と 3 と 4 である
イ 2 である
ウ 2 と 3 である
エ 2 と 3 と 4 である
オ 2 と 4 である
カ ない
設問 3
次の記述中のに入れる正しい答えを,解答群の中から選べ。
![](../../wp-content/uploads/2021/10/h29a_q8_figure_1.jpg)
〔考え方〕
文字列長が n である m 個の文字列について考える。文字列に対して, (m + 1) 行 (n + 1) 列の表を用意する。以後,この表を検査文字付表という。
- 1. 検査文字の生成
- 例えば,文字列長が 5 である 4 個の文字列 ipa␣␣ ,tests , make␣ ,it.␣␣ を,図 1 の太枠内のように,各文字列の先頭の位置を最左列に揃え,各文字列を上の行から順に格納して,表を作成する。この表の太枠内の各行各列をそれぞれ文字列とみなして検査文字を生成し,最右列と最下行に格納する。
この手順で作成した検査文字付表を図 2 に示す。作成した検査文字付表の 5 行 5 列目 (網掛け部分) の検査文字はeである。
図 2 完成した検査文字付表 - 2. 検査文字付表の検証
- 1. で作成した検査文字付表の,最下行を除く各行と最右列を除く各列を文字列とみなし,それぞれ関数 validateCheckCharacter で検証した結果,全て誤りがないと判定された場合には,検査文字付表に誤りがないと判定する。一つでも誤りがあると判定された場合は,検査文字付表に誤りがあると判定する。
e に関する解答群
ア j イ k ウ l エ m
設問 4
次の記述中のに入れる正しい答えを,解答群の中から選べ。
![](../../wp-content/uploads/2021/11/h29a_q8_figure_3.jpg)
図 3 1 行目を取り除いた検査文字付表
f に関する解答群
ア 1 と 2 と 3 と 4 である
イ 2 である
ウ 2 と 3 である
エ 2 と 3 と 4 である
オ 2 と 4 である
カ ない
問題のヒント
文字列の誤りを検出するために、検査文字の生成および検証を行うプログラムです。データの誤りの検出方法には、チェックサム、チェックディジット、ハミング符号、 CRC などがありますが、ここでは、出題者独自の方法が使われています。
問題の前半部は、プログラムの穴埋めです。
検査文字の生成と検証の手順が詳しく示されているので、その手順とプログラムを対応付ければ、穴埋めができるでしょう。その際に、プログラムの変数名に注目してください。
たとえば、 is_even は「偶数である」という意味で、 is_odd は「奇数である」という意味です。これらの変数名が、プログラムを読み取るヒントになります。
問題の後半部は、検査文字の生成と検証の手順に従って、具体的な文字列で検査文字の生成と検証を行う、という内容です。少し時間がかかると思いますが、手作業で丁寧に検査文字の生成と検証を行ってください。
全体として、問題に示された手順を読み取ることが重要な問題です。
みんなの解答欄
こちらから解答できます!
今週の金曜に解答解説ページを、ご解答頂いた方の正解率とともに公開します !!
label 関連タグ
免除試験を受けた 74.9% の方が、 科目A免除資格を得ています。
![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/11/ans_this_weeks_exercise_h29a_algorithm_cover-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/this_weeks_exercise_h29a_algorithm_cover-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/ans_this_weeks_exercise_h30h_algorithm_cover-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_this_weeks_exercise_h29h_algorithm-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_ans_this_weeks_exercise_h29a_algorithm-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム 整数式の解析と計算 2018 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_this_weeks_exercise_h29a_algorithm-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム 整数式の解析と計算 2018 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_ans_this_weeks_exercise_h30h_algorithm-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_this_weeks_exercise_h30h_algorithm-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_ans_this_weeks_exercise_h29a_sec-150x150.jpg)
今週の午後問題〔解答〕情報セキュリティ SSH による通信 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/09/cover_this_weeks_exercise_h29a_sec-150x150.jpg)
今週の午後問題〔問題〕情報セキュリティ SSH による通信 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/fe/fenavi/wp-content/uploads/2019/10/icon_fenavi.png)
- 基本情報技術者試験 の受験勉強をレポート頂ける方を募集中です!
- ツイッター で過去問を配信しています
姉妹サイト 「IT資格の歩き方」 では応用情報技術者以上の情報処理技術者試験の対策記事があります!
基本情報技術者試験を合格されたら、「IT資格の歩き方」で末永く、スキルアップにお役立てください!