FE SUBJECT B
基本情報技術者 科目Bの問題解説：次の手続 hashScore() を実行したときの戻り値はど…
問題
次の手続 hashScore() を実行したときの戻り値はどれか。線形探索法で衝突を処理する。
○整数型: hashScore()
整数型の配列: key ← {10, 17, 24, 5, 12}
整数型の配列: table[1..7] ← すべて空
整数型: i, p
for (i を 1 から keyの要素数 まで 1ずつ増やす)
p ← (key[i] mod 7) ＋ 1
while (table[p] が空でない)
p ← p ＋ 1
if (p ＞ 7)
p ← 1
endif
endwhile
table[p] ← key[i]
endfor
return table[6] ＋ table[1]- ア 29
- イ 31
- ウ 36（正解）
- エ 41
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：36
ハッシュ位置は (key mod 7)+1 です。10は4、17は4が埋まっているので5、24は4と5が埋まっているので6に入ります。5は6が埋まっているので7、12は6と7が埋まり、末尾を越えて1に入ります。したがって table[6]=24、table[1]=12 で、戻り値は36です。
31は12の循環配置を見落とした場合、29は5を table[6] と誤って使った場合に出やすい値です。41は24と17など衝突途中の値を足した誤りです。
線形探索法では、衝突したら次の位置へ進みます。末尾を越えたら1へ戻るので、循環する処理を表に書くとミスを防げます。
仕組みの背景：これはオープンアドレス法（開番地法）の線形探索法です。この問題では本来の位置がp=4やp=6に集中するため、table[4]〜table[7]、さらに1へと連続して埋まる「一次クラスタリング」が起きています。空きが残っていてもこうした連なりが伸びると探索回数が増えるので、表の使用率（5/7）が高いほど衝突処理の手間が増える点が特徴です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。