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

問題文

次の規則に従って配列の要素A[0], A[1], ..., A[9]に正の整数

k

を格納する。

k

として16, 43, 73, 24, 85を順に格納したとき、85が格納される場所はどこか。ここで、

x

mod

y

は

x

を

y

で割った剰余を返す。また、配列の要素は全て0に初期化されている。　〔規則〕　(1) A[

k

mod 10] = 0ならば、

k

→ A[

k

mod 10]とする。　(2) (1)で格納できないとき、A[(

k

+1) mod 10] = 0ならば、

k

→ A[(

k

+1) mod 10]とする。　(3) (2)で格納できないとき、A[(

k

+4) mod 10] = 0ならば、

k

→ A[(

k

+4) mod 10]とする。

選択肢

ア：A[3]

イ：A[5]

ウ：A[6]

エ：A[9]（正解）

##: 配列格納規則の判定【午前2 解説】

要点まとめ

結論：与えられた5つの $k$ を順に格納すると 85 は A[9] に格納され、選択肢はエが正解です。
根拠：各 $k$ について $k mod 10$ をまず確認し、空でなければ $(k + 1) mod 10$ 、さらに空でなければ $(k + 4) mod 10$ を順に試す規則に従います。
差がつくポイント：衝突処理の順序を厳密に守り、 $(k + 1) mod 10$ と $(k + 4) mod 10$ を計算ミスなく判定することが重要です。

正解の理由

初期状態で A[0]～A[9] はすべて 0（空）です。規則に従って順に格納すると以下のようになります。

16 → $16 mod 10 = 6$ 、A[6] が空なので A[6]=16。
43 → $43 mod 10 = 3$ 、A[3] が空なので A[3]=43。
73 → $73 mod 10 = 3$ 、A[3] は埋まっているため $(73 + 1) mod 10 = 4$ を確認、A[4]=73。
24 → $24 mod 10 = 4$ 、A[4] は埋まっているため $(24 + 1) mod 10 = 5$ を確認、A[5]=24。
85 → $85 mod 10 = 5$ 、A[5] は埋まっているため $(85 + 1) mod 10 = 6$ を確認、A[6] も埋まっているため $(85 + 4) mod 10 = 9$ を確認、A[9] は空なので A[9]=85。

したがって 85 が格納されるのは A[9] で、選択肢はエが正解です。

よくある誤解

(1) $(k + 1) mod 10$ と $(k mod 10) + 1$ の違いを意識せず計算ミスすること。実際は同値ですが桁落ちを誤ると誤答に繋がります。
(2) 衝突解決を無限に線形探索すると誤解する場合。問題では最大で3つの候補（ $k mod 10$ , $(k + 1) mod 10$ , $(k + 4) mod 10$ ）のみです。
(3) 配列の初期値を 0 とする点を見落とし、空＝0 であることを忘れて誤判定することがあります。

解法ステップ

配列 A[0..9] を 0 で初期化された状態と確認する。
各値 $k$ を順に処理する（ここでは 16, 43, 73, 24, 85）。
まず $i_{1} = k mod 10$ を計算し A[ $i_{1}$ ] が 0 なら格納。
A[ $i_{1}$ ] が 0 でない場合は $i_{2} = (k + 1) mod 10$ を計算し A[ $i_{2}$ ] を確認。
さらに埋まっている場合は $i_{3} = (k + 4) mod 10$ を計算し A[ $i_{3}$ ] を確認、空なら格納。
問題文の範囲ではここまでで格納されるはずなので結果のインデックスを報告する。

（今回の具体的な配置）

A[6]=16, A[3]=43, A[4]=73, A[5]=24, A[9]=85

選択肢別の誤答解説

ア: A[3] — 43 が A[3] に格納されているため、85 はここには入りません。73 の衝突元と混同すると選びがちです。
イ: A[5] — 24 が A[5] に入っているので 85 はここでは止まりません。 $85 mod 10 = 5$ の衝突を見落とした誤答です。
ウ: A[6] — 16 が A[6] にあるため誤りです。85 の $(k + 1) mod 10 = 6$ を確認して満たされないことを忘れるとここを選びます。
エ: A[9] — 正解。上の手順で $(85 + 4) mod 10 = 9$ により A[9] が最終格納位置になります。

補足コラム

この問題はハッシュ法の衝突解決（オープンアドレッシング）の一種を簡略化した例です。典型的には線形探索（

i + 1

）や二次探索を使いますが、本問は固定された3つの候補順で探索します。実務やアルゴリズム試験では「探索順序」と「剰余計算」を正確に扱う練習が有効です。

FAQ

Q1:

(k + 1) mod 10

と

k mod 10 + 1

は同じですか？
A1: はい。数学的に

(k + 1) mod 10 \equiv (k mod 10 + 1) mod 10

で同値です。ただし最終的に 0〜9 の範囲に収める点に注意してください。

Q2: もし3候補とも埋まっていたら？
A2: 問題文では3つの候補までしか規定されていません。一般的には「格納不可」と扱いますが、設問ごとに扱いを確認してください。

Q3: 配列の空判定が 0 である理由は？
A3: 問題文に「配列の要素は全て0に初期化されている」と明記されており、正の整数

k

が格納されるため 0 は空の印と見なせます。

関連キーワード: ハッシュ法、衝突解決、剰余算、開番地法、配列インデックス、線形探索

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！