アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20180610 実施分 問19
格納アドレスが 1〜6 の範囲の直接編成ファイルにおいて,次の条件でデータを格納した場合,アドレス 1 に格納されているデータのキー値はどれか。
〔条件〕
(1) キー値が 3,4,8,13,14,18 の順でデータを格納する。
(2) データのキー値を 5 で割った余りに 1 を加えた値を格納アドレスにする。
(3) 格納アドレスに既にデータがある場合には,次のアドレスに格納する。これを格納できるまで繰り返す。最終アドレスの次は先頭とする。
(4) 初期状態では,ファイルは何も格納されていない。
答えを選ぶ
出典:基本情報技術者試験 科目A免除 修了試験 20180610 実施分 問19(問題文は IPA の公開問題。解説は当サイト作成)
答えと解説を見る
正解:イ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
オープンアドレス法では衝突時に次のアドレスへ順に探し、最終アドレスの次は先頭に戻る。
この問題で必要なこと
アドレス=キー mod 5 +1。3→4、4→5、8→4衝突→5衝突→6、13→4→5→6→1、14→5→6→1→2、18→4,...→3。アドレス1は13。
ひっかけ
格納順序を取り違えると別のキーが残る。
この知識の出題:本試験系 3 回・免除試験 7 回(公開問題での観測値)