令和5年度 公開問題 科目B 問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] |
出典:令和5年度 基本情報技術者試験 科目B 公開問題 問4
正解と解説を見る
正解:エ
ポイント:ハッシュ表:まず1つ目の関数で位置を決め、埋まっていたら2つ目の関数の位置に入れる。位置は「mod 要素数」+1。
hashArray は要素数5で、全部 -1(空き)から始めます。
add(3):calcHash1 = (3 mod 5)+1 = 4。hashArray[4] は空きなので 3 を入れる。→ {-1, -1, -1, 3, -1}
add(18):calcHash1 = (18 mod 5)+1 = 4。hashArray[4] は 3 で埋まっている。calcHash2 = ((18+3) mod 5)+1 = 2。空きなので 18 を入れる。→ {-1, 18, -1, 3, -1}
add(11):calcHash1 = (11 mod 5)+1 = 2。hashArray[2] は 18 で埋まっている。calcHash2 = ((11+3) mod 5)+1 = 5。空きなので 11 を入れる。→ {-1, 18, -1, 3, 11}
よって(エ)。
よくある間違い:「+1」を忘れて、位置を1つずつ前にずらしてしまう(配列の要素番号は1から始まるので、mod の結果 0〜4 に 1 を足して 1〜5 にしています)。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。