応用情報技術者 2013年 春期 午前2 問05

探索表の構成法と最適探索手法の組合せ【午前2 解説】

要点まとめ

• 結論：コード順の探索表は2分探索、使用頻度順は線形探索、コードから一意に決まる場所はハッシュ表探索が最適です。
• 根拠：2分探索は整列済みデータに有効、線形探索は頻度順で高速化、ハッシュ表は直接アクセスで高速検索が可能です。
• 差がつくポイント：探索表の構成と探索手法の特性を正しく理解し、適材適所で使い分けることが合格の鍵です。

正解の理由

• aの探索表はコード順に整列されているため、2分探索が効率的です。
• bは使用頻度順に並んでおり、頻繁にアクセスされるデータが先頭にあるため線形探索でも高速に見つかります。
• cはコードから一意に格納場所が決まるため、ハッシュ表探索が最適で直接アクセスが可能です。
  以上より、選択肢アの組合せが最も適切です。

よくある誤解

• 「使用頻度順なら2分探索が速い」と誤解しがちですが、整列されていないため2分探索は使えません。
• ハッシュ表は必ず高速とは限らず、衝突処理の理解が必要です。

解法ステップ

1. 探索表aの構成を確認し、コード順に整列されていることを把握する。
2. 探索表bは使用頻度順で整列されていないため、線形探索が適していると判断する。
3. 探索表cはコードから格納場所が一意に決まるため、ハッシュ表探索が最適と判断する。
4. 各探索手法の特徴と探索表の構成を照らし合わせ、最適な組合せを選ぶ。

選択肢別の誤答解説

• イ：bにハッシュ表探索を選んでいるが、使用頻度順でハッシュ表は不適切。
• ウ：aに線形探索を選んでいるが、コード順なら2分探索の方が効率的。
• エ：cに2分探索を選んでいるが、コードから一意に決まる場合はハッシュ表探索が適切。

補足コラム

• 2分探索は整列済みデータに対して$O(\log n)$の探索時間を持ちます。
• 線形探索は整列不要で単純ですが、平均$O(n)$の時間がかかります。
• ハッシュ表はハッシュ関数により直接アクセスでき、平均$O(1)$の高速探索が可能ですが、衝突処理が重要です。

FAQ