| 基本情報技術者試験 |
2006年度 ＝ 平成18年度・秋期 |
午前 |
問15 |
次の規則に従って配列の要素A [0], A [1], … , A [9]に正の整数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]
|
エ
ハッシュ法は、キー値に対して何らかの変換関数を適用することによって、そのデータを格納する位置（レコード番号や配列の添字など）を求める手法です。なお、変換関数のことをハッシュ関数と呼びます。
本問では、規則(1)によって、値を10で割った剰余を格納先とします。ただし、剰余が同一のデータは、格納先が衝突するため、規則(2)および規則(3)によって格納先を調整することになっています。
■Step 1 16を格納する。
16 mod 10は6です。16をA [6]に格納します。
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │ │ │ │１６│ │ │ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
■Step 2 43を格納する。
43 mod 10は3です。43をA [3]に格納します。
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │４３│ │ │１６│ │ │ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
■Step 3 73を格納する。
73 mod 10は3です。A [3]は既に埋まっていますので、規則(2)を用います。(73 + 1) mod 10は4です。73をA [4]に格納します。
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │４３│７３│ │１６│ │ │ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
■Step 4 24を格納する。
24 mod 10は4です。A [4]は既に埋まっていますので、規則(2)を用います。(24 + 1) mod 10は5です。24をA [5]に格納します。
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │４３│７３│２４│１６│ │ │ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
■Step 5 85を格納する。
85 mod 10は5です。A [5]は既に埋まっていますので、規則(2)を用います。(85 + 1) mod 10は6です。A [6]も既に埋まっていますので、規則(3)を用います。(85 + 4) mod 10は9です。85をA [9]に格納します。
０ １ ２ ３ ４ ５ ６ ７ ８ ９
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │４３│７３│２４│１６│ │ │８９│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
正解はエです。
