平成25年度春期問7テクノロジ系

基本情報平成25年度春期問7：テクノロジ系に関する問題

次の規則に従って配列の要素 4[O], 4[1], .…. , 4[9] に正の整数 z を格納する。ヵとして 16, 43, 73, 24, 85 を順に格納したとき, 85 が格納される場所はどこか。ここで, * mod y は, * をヶで割った剰余を返す。また, 配列の要素は全て 0 に初期化されている。 [規則] (1) 4[z mod 10] ニ 0 ならば, * を4[z mod 10] に格納する。 (2②) Q①)で格納できないとき, 4[@十1) mod 10] ニ 0ならば, ヵを4[%十1) mod 10] に格納する。 (3③ (②⑫②で格納できないとき, 4[%十4) mod 10] ニ 0ならば, ょを4[%二2 mod 10] に格納する。

a4[3]
b4[5]
c4I[6]
d4[9]正答

正答：D4[9]

AI解説（初心者・標準・上級）

理解度に合わせて3レベルの解説を無料で読めます。

初心者向けまずはここから。やさしく要点を解説

答えは d「A[9]」 です。

10個の場所（A[0]〜A[9]）に数字を入れていきます。ルールは「割り算の余りの場所に空きがあれば入れる、無ければ別の場所を試す」。

16 → 16÷10=余り6 → A[6] 空き → A[6] に格納
43 → 余り3 → A[3] 空き → A[3] に格納
73 → 余り3 → A[3] 埋まってる → 次の規則で別の場所へ
24 → 余り4 → A[4] 空き → A[4]
85 → 余り5 → A[5] 空き、と思いきや…

計算の結果、最後の85は A[9] に入ります（規則(3)が適用された結果）。

👉 覚え方：「ハッシュ法＝余りで場所を決め、空いてなければ次を試す（オープンアドレス法）」。

標準試験対策の基準レベル

なぜこれが正解か

正解は d A[9]。本問はハッシュ法（オープンアドレス法）の典型問題で、規則を順次適用：

(1) A[x mod 10] が空なら格納
(2) ダメなら A[(x+1) mod 10] が空なら格納
(3) それもダメなら A[(x+4) mod 10] が空なら格納

順次追跡：

x=16：16 mod 10=6 → A[6]空き → A[6]=16
x=43：43 mod 10=3 → A[3]空き → A[3]=43
x=73：73 mod 10=3 → A[3]埋まり → (3+1) mod 10=4 → A[4]空き → A[4]=73
x=24：24 mod 10=4 → A[4]埋まり → (4+1) mod 10=5 → A[5]空き → A[5]=24
x=85：85 mod 10=5 → A[5]埋まり → (5+1) mod 10=6 → A[6]埋まり → (5+4) mod 10=9 → A[9]空き → A[9]=85

各選択肢の解説

a A[3]：43の場所、85は規則(3)まで進む。
b A[5]：24の場所、85はさらに次へ。
c A[6]：16の場所、85は最終的にA[9]へ。
d A[9]：規則(3)で +4 シフトの結果。

覚え方・ひっかけ注意

ハッシュ法は「衝突発生時のリハッシュ規則」が肝。本問は規則が(1)→(2)→(3)で段階的適用される設計。衝突解決方式には他に連鎖法（チェイン法）もある。値を表に書きながら順次トレースすれば確実に解ける。

上級誤答論破・背景理論まで深掘り

理論的背景

ハッシュ法は、ハッシュ関数 h(key) で格納位置を直接計算する直接参照型データ構造で、平均O(1) の検索・挿入・削除を実現。本問は オープンアドレス法（open addressing） で、衝突時に別の位置を順次試行する方式。試行関数の取り方で：

線形探査法（linear probing）：h(k), h(k)+1, h(k)+2, ... と連続位置を試行（本問の規則(1)(2)）
二次探査法（quadratic probing）：h(k), h(k)+1², h(k)+2², ... と平方刻みで試行
ダブルハッシュ法：別のハッシュ関数で間隔を決定

本問の規則(3)は +4 シフトで、線形と非線形の混合パターン。代替手法として 連鎖法（separate chaining） は衝突値を連結リストで保持。

実務での使われ方

ハッシュテーブルは現代の標準データ構造で、JavaのHashMap、PythonのDict、C++のunordered_map、JavaScriptのObjectなど。ハッシュ関数の質（一様分布性）が性能を左右し、MurmurHash、xxHash、SipHash等が実用ハッシュ関数。暗号学的用途ではSHA-256、SHA-3が使われる。ロードファクタ（使用率 = 要素数/配列サイズ）が0.7を超えると衝突急増のため、動的拡張（resize、rehash）で性能維持。

試験での位置づけ

FE・APアルゴリズム分野で頻出。ハッシュ関数、衝突解決法、オープンアドレス vs 連鎖法の比較、平均/最悪計算量、ロードファクタ、再ハッシュ条件が定番。応用情報・データベーススペシャリストではB木・B+木との比較、データベースインデックス（ハッシュインデックスvs B木インデックス）、分散ハッシュテーブル（DHT、コンセンサスハッシュ）まで踏み込む。