FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の線形探索法のハッシュ表で，11を見つけるまでの参照回数はどれか。
整数型の配列: table[0..7] ← {空, 空, 空, 空, 空, 空, 空, 空}
整数型の配列: keys ← {10, 18, 26, 3, 11}
for (keysの各要素 k を先頭から順に取り出す)
i ← k mod 8
while (table[i] が空でない)
i ← (i + 1) mod 8
endwhile
table[i] ← k
endfor
probe ← 1
i ← 11 mod 8
while (table[i] ≠ 11)
i ← (i + 1) mod 8
probe ← probe ＋ 1
endwhile
return probe- ア 2
- イ 3
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
正解：4
10,18,26はいずれもmod 8が2なので，2,3,4へ順に入る。3は本来位置3だが埋まっているため5へ入る。11は本来位置3から探索を始め，3,4,5,6を確認して見つかる。
| キー | 格納位置 | 理由 |
|---|---|---|
| 10 | 2 | 空き |
| 18 | 3 | 2が衝突 |
| 26 | 4 | 2,3が衝突 |
| 3 | 5 | 3,4が衝突 |
| 11 | 6 | 3,4,5が衝突 |
11の探索は位置3から始まり，4回目の参照で見つかる。
選択肢の見分け方：2や3は途中の衝突列で止めた値，5は空き位置まで余分に進めた値である。探索では目的キーを見つけた時点の参照回数を返す。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。