FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の線形探索法のハッシュ表で、11を見つけるまでの参照回数は…
問題
次の線形探索法のハッシュ表で、11を見つけるまでの参照回数はどれか。
整数型の配列: table[0..7] ← {空, 空, 空, 空, 空, 空, 空, 空}
整数型の配列: keys ← {10, 18, 26, 3, 11}
for (keysの各要素 k を先頭から順に取り出す)
i ← k mod 8
while (table[i] が空でない)
i ← (i + 1) mod 8
endwhile
table[i] ← k
endfor
probe ← 1
i ← 11 mod 8
while (table[i] ≠ 11)
i ← (i + 1) mod 8
probe ← probe ＋ 1
endwhile
return probe- ア 2
- イ 3
- ウ 4（正解）
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
10,18,26はいずれもmod 8が2なので、2,3,4へ順に入ります。3は本来位置3ですが埋まっているため5へ入ります。11は本来位置3から探索を始め、3,4,5,6を確認して見つかります。
| キー | 格納位置 | 理由 |
|---|---|---|
| 10 | 2 | 空き |
| 18 | 3 | 2が衝突 |
| 26 | 4 | 2,3が衝突 |
| 3 | 5 | 3,4が衝突 |
| 11 | 6 | 3,4,5が衝突 |
11の探索は位置3から始まり、4回目の参照で見つかります。
選択肢の見分け方：2や3は途中の衝突列で止めた値、5は空き位置まで余分に進めた値です。探索では目的キーを見つけた時点の参照回数を返します。
なぜ回数が増えるのか：この表はハッシュ値が衝突したとき次の空きへずらして格納する線形探索法（オープンアドレス法）です。10・18・26・3がmod 8＝2や3に集中したため、位置2〜6に連続した塊（一次クラスタ）ができています。11も本来位置3から塊を端までたどるので、参照が4回まで伸びてしまうのです。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。