アルゴリズムとプログラミング

基本情報技術者試験 科目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 回(公開問題での観測値)

この知識をアプリで解いて覚える レッスン「ハッシュ法と衝突の扱い」で学ぶ

同じ知識の過去問