2010年度 秋期 システムアーキテクト 午前I 問3

bの「コードの使用頻度順に格納した探索表」は、使用頻度の高いデータが先頭に近いほど効率が良いという特性を示唆しており、これはハッシュ表探索における衝突解決を考慮した配置や、頻度に基づいたアクセス効率の最適化とも関連しますが、一般的にコードから直接位置が決まるものではなく、頻度順に格納することで、頻繁にアクセスされるデータが探索の初期段階で見つかりやすくなり、平均計算量を改善する効果が期待できます。ハッシュ表探索の平均計算量は、理想的にはO(1)ですが、衝突が多い場合はO(n)に近づきます。

cの「コードから一意に決まる場所に格納した探索表」は、コード値から直接格納場所が計算できる、いわゆるハッシュ表の構造を示しています。ハッシュ表探索は、コード（キー）をハッシュ関数に通すことで直接データ（値）の格納場所を計算するため、理想的には探索計算量はO(1)となります。

誤った選択肢について分析します。

アは、aを2分探索、bを線形探索、cをハッシュ表探索としていますが、cはコードから一意に決まる場所に格納しているため、ハッシュ表探索が最も適切であり、線形探索ではありません。線形探索はO(n)の計算量であり、cの構造には不向きです。

イは、aを2分探索、bをハッシュ表探索、cを線形探索としていますが、cの「コードから一意に決まる場所」という構造はハッシュ表探索の概念に合致するため、線形探索とするのは誤りです。

エは、aを線形探索、bをハッシュ表探索、cを2分探索としていますが、aはコード順に格納されているため、線形探索よりも効率の良い2分探索が適しており、不適切です。また、cはコードから一意に場所が決まるため、2分探索よりもハッシュ表探索が適しています。