アルゴリズムとプログラミングアルゴリズムとデータ構造

サイズ7のハッシュテーブルでダブルハッシュ法を使用する。h1(k)=k mod 7、h2(k)=1+(k mod 5)。スロット1がすでに占有されている状態でキー36を挿入するとき、最終的に格納されるインデックスはどれか。

ア.インデックス3正解

イ.インデックス2

ウ.インデックス5

エ.インデックス0

解説

ダブルハッシュは「二段階の宝探し」。最初のマップで場所を決め、衝突したら2番目のマップのステップ幅で進む。

なぜアが正解か

h1(36)=36 mod 7=1 → スロット1は占有済み → 衝突。h2(36)=1+(36 mod 5)=1+1=2。次の探査位置: (1+1×2) mod 7=3 mod 7=3 → スロット3が空なので格納。答えはインデックス3。

なぜイは間違いか

インデックス2は誤り。ダブルハッシュではステップ幅h2=2を使うので(1+2)mod7=3になる。

なぜウは間違いか

インデックス5は誤り。2回目の探査位置(1+2×2)mod7=5になるが、1回の探査で空きが見つかる。

なぜエは間違いか

インデックス0は誤り。計算上(1+n×2)mod7でインデックス0になるには複数回の衝突が必要で、スロット3で見つかる。

出典: AI生成問題（学習用）

← 前の問題

サイズ7のハッシュテーブル（インデックス0〜6）に線形探査法でキー15, 22, 8, 29を順番に挿入する。ハッシュ関数 h(k) = k mod 7 を使用する。挿入後のテーブルの状態として正しいものはどれか。

次の問題 →

5頂点のグラフでダイクストラ法を使い頂点Aから頂点Eへの最短路を求める。辺の重みは A-B=4, A-C=2, B-D=3, B-E=6, C-D=1, C-E=5, D-E=2 とする。A→Eの最短距離はどれか。