基本情報技術者 2013年 秋期 午前（科目A） 問07
問題文
次の規則に従って配列の要素に正の整数を格納する。として16, 43, 73, 24, 85を順に格納したとき、85が格納される場所はどこか。ここで、は、をで割った剰余を返す。また、配列の要素は全て0に初期化されている。
〔規則〕
(1) ならば、をに格納する。
(2) (1)で格納できないとき、ならば、をに格納する。
(3) (2)で格納できないとき、ならば、をに格納する。
選択肢
ア：
イ：
ウ：
エ：（正解）
配列への格納規則（衝突解消の手順）【午前2 解説】
要点まとめ
- 結論: 85 は A[9] に格納される。衝突時は順に , , を確認し、最初に空いている位置へ格納するため。
- 根拠: 16→、43→、73 は が埋まるので に入り、24 は が埋まるため に入るという逐次判定の流れがあるため。
- 差がつくポイント: 各ステップで必ず提示順の3つの位置のみを確認する点と、剰余計算(\mod)の結果を正確に行うことが正解を左右する。
正解の理由
正解は エ です。順に格納すると
- 16 は で A[6] に格納、
- 43 は で A[3] に格納、
- 73 は が埋まっているため （A[4]）に格納、
- 24 は が埋まっているため （A[5]）に格納、
- 85 は が埋まっているため （A[6]）も埋まっており、最後に （A[9]）が空いているのでそこに格納されます。よって A[9] が格納位置です。
よくある誤解
- 「(2) がダメなら最初に戻って再計算する」と誤解し、別の順序で探索してしまう。必ず提示された順序でのみ確認する。
- や の計算をせず、単に の周辺インデックスを順に見てしまう（例えば +1, +2 と誤認する）。
- 配列が 0 初期化であることを忘れ、非ゼロ判定を誤ると格納位置がずれる。
解法ステップ
- 配列 A[0]..A[9] は全て 0 から開始。挿入を順に処理する。
- 各 についてまず を計算し、A[] が 0 なら格納。違えば次へ。
- 次に を計算し、A[] が 0 なら格納。違えば次へ。
- 最後に を計算し、A[] が 0 なら格納。全て埋まっていれば規則外（本問では該当なし）。
- 与えられた順で 16, 43, 73, 24, 85 を上記手順で処理し、それぞれの格納先を確定する。
（具体的な途中状態）
- 16: → A[6]=16
- 43: → A[3]=43
- 73: (埋) → → A[4]=73
- 24: (埋) → → A[5]=24
- 85: (埋) → (埋) → → A[9]=85
選択肢別の誤答解説
- ア: A[3] — 43 が A[3] に入るため 85 が A[3] に入ることはない。85 の で最初は A[5] を確認するため不正解。
- イ: A[5] — 24 が既に A[5] に格納されており、85 の第一候補 A[5] は埋まっているため不正解。
- ウ: A[6] — 16 が A[6] に格納済みで、85 の第二候補 は埋まっているため不正解。
- エ: A[9] — 正解。85 は第一候補 A[5]、第二候補 A[6] が埋まっており、第三候補 に格納される。
補足コラム
この問題はハッシュ法のオープンアドレッシング（衝突解消）の簡易版と考えられます。典型的な各種探索順（線形探索、二次探索、疑似乱数探索など）とは異なり、本問は固定された優先順位（, , ）で探索する点が特徴です。試験問題では「指定された順序どおりに」厳密に評価すればよく、余計な仮定は禁物です。
FAQ
Q1: はなぜ最後に見るのですか？
A1: 問題の規則でそう定められているためです。提示順を変えると格納位置が変わる可能性があります。
A1: 問題の規則でそう定められているためです。提示順を変えると格納位置が変わる可能性があります。
Q2: 全て埋まっていた場合はどうなる？
A2: 本問では該当しませんが、実装的には格納失敗またはエラー処理になります。規則が続くなら追加の試行方法が必要です。
A2: 本問では該当しませんが、実装的には格納失敗またはエラー処理になります。規則が続くなら追加の試行方法が必要です。
Q3: マイナスやゼロの は扱えるか？
A3: 本問は正の整数 が前提です。負数や 0 を扱う場合は剰余の定義に注意が必要です。
A3: 本問は正の整数 が前提です。負数や 0 を扱う場合は剰余の定義に注意が必要です。
関連キーワード: 配列格納, 衝突解消, オープンアドレッシング, 剰余演算, 探索順, ハッシュ衝突, modulo, 実装演習
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！