基本情報技術者 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]（正解）

🔒 解説は解答すると表示されます

線形探索による配列格納【午前解説】

正解の理由

初期状態で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] で、選択肢はエが正解です。

解法ステップ

配列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] が最終格納位置になります。

よくある誤解

(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であることを忘れて誤判定することがあります。

補足コラム

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

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は空の印と見なせます。

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

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！