アルゴリズムとプログラミング
平成28年度 秋期 基本情報技術者試験 午前 問20
格納アドレスが 1～6 の範囲の直接編成ファイルにおいて，次の条件でデータを格納した場合，アドレス 1 に格納されているデータのキー値はどれか。
〔条件〕
(1) キー値が 3，4，8，13，14，18 の順でデータを格納する。
(2) データのキー値を 5 で割った余りに 1 を加えた値を格納アドレスにする。
(3) 格納アドレスに既にデータがある場合には，次のアドレスに格納する。これを格納できるまで繰り返す。最終アドレスの次は先頭とする。
(4) 初期状態では，ファイルは何も格納されていない。
答えを選ぶ
出典：平成28年度 秋期 基本情報技術者試験 午前 問20（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：イ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
オープンアドレス法は衝突時に次の空き番地へ順に格納し、末尾の次は先頭に戻る。
この問題で必要なこと
3→4,4→5,8→4が衝突し6,13→4が衝突し1へ(5,6は使用済み),14→5衝突しさらに2へ…と順にたどる。13が先に入るためアドレス1は13。
ひっかけ
剰余+1の計算ミスや、格納順序(13と14の順)を取り違えさせる。
この知識の出題：本試験系 3 回・免除試験 7 回（公開問題での観測値）。頻出知識ランキング170位（全1,254件中）。