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