基本情報技術者試験 科目Bの「令和5年度 サンプル問題 問4」(ハッシュ法・mod を使った配列への格納)を、図解トレースで解説します。calcHash1・calcHash2 のような 処理が1行だけの関数は、計算式を直接トレース してしまうのがコツです。
動画で見たい方はこちら▼
問題(令和5年度 サンプル問題 問4)
次の記述中の【 】に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
関数 add は，引数で指定された正の整数 value を大域の整数型の配列 hashArray に格納する。格納できた場合は true を，できなかった場合は false を返す。整数 value を hashArray のどの要素に格納すべきかを，関数 calcHash1 及び calcHash2 を利用して決める。手続 test は，関数 add を呼び出して hashArray に正の整数を格納する。手続 test の処理が終了した直後の hashArray の内容は，【 】である。
大域: 整数型の配列: hashArray
○ 論理型: add(整数型: value)
整数型: i ← calcHash1(value)
if (hashArray[i] = -1)
hashArray[i] ← value
return true
else
i ← calcHash2(value)
if (hashArray[i] = -1)
hashArray[i] ← value
return true
endif
endif
return false
○ 整数型: calcHash1(整数型: value)
return (value mod hashArray の要素数) + 1
○ 整数型: calcHash2(整数型: value)
return ((value + 3) mod hashArray の要素数) + 1
○ test()
hashArray ← {5個の -1}
add(3)
add(18)
add(11)
解答群
ア {−1, 3, −1, 18, 11}
イ {−1, 11, −1, 3, −1}
ウ {−1, 11, −1, 18, −1}
エ {−1, 18, −1, 3, 11}
オ {−1, 18, 11, 3, −1}
Memo: 本番では「参考資料」で演算子や擬似言語の仕様を確認できる
本番のCBT画面には「参考資料」のボタンがあり、mod(剰余)などの演算子や、if文・while文といった擬似言語の前提仕様を確認できます。ただし本番中にじっくり読む時間はありません。mod のようによく出るものは「余りを求める」と覚えておき、参考資料は「忘れたときの保険」くらいに考えておきましょう。
本番さながらの環境で解いてみたい方はこちら↓
解説
正解はエ {−1, 18, −1, 3, 11} です。
①トレース表の作成
| i | value | if(hashArray[i] = -1) |
|---|---|---|
hashArray
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| -1 | -1 | -1 | -1 | -1 |
②add(3)のトレース
| i | value | if(hashArray[i] = -1) |
|---|---|---|
| 3 |
③i ← calcHash1(value)
| i | value | if(hashArray[i] = -1) |
|---|---|---|
4 |
3 |
④if (hashArray[i] = -1)の判定
| i | value | if(hashArray[i] = -1) |
|---|---|---|
4 |
3 | -1 ○ |
⑤hashArray[i] ← value
hashArray
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| -1 | -1 | -1 | -1 | |
| 3 |
(return true)
⑥(add(18)のトレース)
i ← calcHash1(value)
if (hashArray[i] = -1)の判定
| i | value | if(hashArray[i] = -1) |
|---|---|---|
4 |
3 | -1 ○ |
| ~~~ | ~~~ | ~~~ |
4 |
18 | 3 × |
⑦×なので､elseの処理に進みます｡
i ← calcHash2(value)
(calcHash2)return ((value + 3) mod hashArray の要素数) + 1
| i | value | if(hashArray[i] = -1) |
|---|---|---|
4 |
3 | -1 ○ |
| ~~~ | ~~~ | ~~~ |
4 |
18 | 3 × |
2 |
⑧if (hashArray[i] = -1)の判定
| i | value | if(hashArray[i] = -1) |
|---|---|---|
4 |
3 | -1 ○ |
| ~~~ | ~~~ | ~~~ |
4 |
18 | 3 × |
2 |
hashArray[2] = -1 -1 ○ |
hashArray[i] ← value
hashArray
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| -1 | -1 | -1 | ||
| 18 | 3 |
⑨add(11)のトレース
| i | value | if(hashArray[i] = -1) |
|---|---|---|
4 |
3 | -1 ○ |
| ~~~ | ~~~ | ~~~ |
4 |
18 | 3 × |
2 |
-1 ○ |
|
| ~~~ | ~~~ | ~~~ |
2 |
11 | 18 × |
5 |
-1 ○ |
hashArray[i] ← value
hashArray
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| -1 | -1 | |||
| 18 | 3 | 11 |
よって正解はエ {−1, 18, −1, 3, 11} です。
Point:処理が1行だけの関数は､直接トレースしてしまう
処理が1行だけの関数は､直接トレースしてしまいましょう｡トレースがシンプルになります｡
関連リンク
関連動画
関数から関数を追う基礎が学べる、同じ章の動画です。
講座の全動画はこちら（プレイリスト）。
6/30まで限定 無料プレゼント
サンプル問題だけ解いても、
合格できません
サンプル問題は応用ばかり。学習には不向きで、非効率です。段階的に学べるオリジナル問題50問を加えた学習専用サイトを、今だけ無料でプレゼント中
⏱ 2分で終わるアンケートに答えるだけ！
▶ アンケートに答えてサイトを受け取る
※ Googleフォーム(SSL)に移動します
