修了試験 2018-06-10実施分 基本情報技術者試験 問19

解説

正解は2です。 直接編成ファイルでは、キー値から計算したアドレスにデータを格納します。 本問では、アドレス＝キー値を5で割った余り＋1です。 衝突（すでにデータがある）したら次のアドレスへ進み、6の次は1に戻ります。 【計算】 キー3は、余り3＋1＝4で、アドレス4に格納します。 キー4は、余り4＋1＝5で、アドレス5に格納します。 キー8は、余り3＋1＝4ですが4と5が埋まっているので、アドレス6に格納します。 キー13は、余り3＋1＝4ですが4、5、6が埋まっているので、先頭に戻ってアドレス1に格納します。 キー14は、余り4＋1＝5ですが5、6、1が埋まっているので、アドレス2に格納します。 キー18は、余り3＋1＝4ですが4、5、6、1、2が埋まっているので、アドレス3に格納します。 【選択肢別解説】 1：× キー8はアドレス6に格納されます。 2：○ キー13は4、5、6で衝突した後、先頭のアドレス1に格納されます。 3：× キー14はアドレス1も埋まっているため、アドレス2に格納されます。 4：× キー18はアドレス3に格納されます。 【ポイント】 衝突時に次の空きアドレスを順に探す方法をオープンアドレス法（線形探査）といいます。 「最終アドレスの次は先頭」という条件を見落とさないことが大切です。