修了試験 2021-12-12実施分 基本情報技術者試験 問19

解説

正解は2です。 キー値から格納アドレスを計算し、衝突したら次のアドレスへ進める方式で格納していく問題です。 格納アドレスは「キー値を5で割った余り＋1」です。 【計算】 キー値3は、3÷5の余り3に1を足してアドレス4に格納します。 キー値4は、余り4に1を足してアドレス5に格納します。 キー値8は、余り3でアドレス4ですが、4と5が使用中なので、アドレス6に格納します。 キー値13は、余り3でアドレス4ですが、4、5、6が使用中です。 最終アドレスの次は先頭なので、アドレス1に格納します。 キー値14は、余り4でアドレス5ですが、5、6、1が使用中なので、アドレス2に格納します。 キー値18は、余り3でアドレス4ですが、4、5、6、1、2が使用中なので、アドレス3に格納します。 【選択肢別解説】 1：× キー値8はアドレス6に格納されます。 アドレス1には届きません。 2：○ キー値13は、アドレス4から6が埋まっているため先頭に戻り、アドレス1に格納されます。 3：× キー値14は、アドレス5、6、1が使用中なので、アドレス2に格納されます。 4：× キー値18は、空きを探して進んだ結果、アドレス3に格納されます。 【ポイント】 衝突時に次のアドレスへ進む方式をオープンアドレス法（線形探査）といいます。 格納順に1件ずつ表を埋めていくと、取り違えずに解けます。