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

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

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

同じ知識の過去問