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