基本情報技術者 2016年 秋期 午前（科目A） 問20

直接編成ファイルにおける格納アドレス計算【午前2 解説】

要点まとめ

• 結論：アドレス1に格納されるキー値は13であり、選択肢は イ（13）が正解です。
• 根拠：ハッシュ関数は「キー値を5で割った余りに1を加える」$($アドレス$= (key \bmod 5)+1$$)で、衝突時は次のアドレスへ順に格納（線形探査）します。
• 差がつくポイント：初回配置順に従い順次線形探査で埋めていくため、ハッシュ先が同じキー群では最初の空きスロットを正確に追うことが合否を分けます。

正解の理由

よくある誤解

• 「余りに1を加えるとアドレスは1〜5だけになる」と考えて5つしか候補がないと思い込み、表の6番目を使う可能性を見落とす。実際は衝突で次のアドレス（6や1へラップ）を使います。
• 「格納順を一括で考える」ために個別の衝突処理を順序無視で計算して誤答になる。与えられた順序で逐次配置する点を忘れないこと。
• 「ハッシュ値だけで最終配置を判断」してしまい、先に入ったデータによる連鎖的な空き位置移動を考慮しない誤り。

解法ステップ

1. ハッシュ関数を確認する：アドレス = $(key\mathrm{mod}5)+1$。
2. 指定の順序でキーを一つずつ格納する。空いていればそのアドレスへ、埋まっていれば次のアドレスへ（最後は先頭に戻る）。
3. 各キーの配置を追跡し、最終的にアドレス1に何が入るかを確定する。
4. 必要なら簡単な表や番号付きリストでアドレス1〜6の状態を逐一書き出す。

• 3 → $(3\mathrm{mod}5)+1=4$ に格納（4:3）
• 4 → $(4\mathrm{mod}5)+1=5$ に格納（5:4）
• 8 → $(8\mathrm{mod}5)+1=4$ は満杯 → 5満杯 → 6空き → 6:8
• 13 → $(13\mathrm{mod}5)+1=4$ は満杯 → 5,6満杯 → 1空き → 1:13
• 14 → $(14\mathrm{mod}5)+1=5$ は満杯 → 6,1満杯 → 2空き → 2:14
• 18 → $(18\mathrm{mod}5)+1=4$ は満杯 → 5,6,1,2満杯 → 3空き → 3:18

選択肢別の誤答解説

• ア: 8
  誤りの理由は、8のハッシュ先はアドレス4で、そこが占有されているため次に回って6に入る点を見落としている場合が多い。8は最終的にアドレス6に配置されます。
• イ: 13（正解）
  正答の根拠は上記の通り。13のハッシュ先4は先行データで埋まっており、線形探査で最初に空いた1に入ります。
• ウ: 14
  14のハッシュ先は5ですが、5・6・1が埋まっているため実際はアドレス2に入ります。アドレス1ではありません。
• エ: 18
  18のハッシュ先は4で、線形探査により最終的にアドレス3に配置されるため、アドレス1と混同してはなりません。

補足コラム

keys = [3,4,8,13,14,18]
table = [None]*6  # addresses 1..6 (index0->addr1)
def addr(k): return (k % 5)
for k in keys:
    i = addr(k)
    while table[i] is not None:
        i = (i+1) % 6
    table[i] = k
print(table)  # -> [13,14,18,3,4,8]

FAQ