応用情報技術者 2018年 秋期 午前2 問08

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

要点まとめ

• 結論：コード順の探索表は2分探索、使用頻度順は線形探索、コード位置決定型はハッシュ表探索が最適です。
• 根拠：2分探索は整列済みデータに有効、線形探索は頻度順で先頭にヒットしやすく効率的、ハッシュ表はコードから直接位置を特定可能です。
• 差がつくポイント：探索表の構造と探索手法の適合性を理解し、探索効率を最大化する選択が重要です。

正解の理由

• aはコード順に整列されているため、2分探索が高速で効率的です。
• bは使用頻度順に並んでおり、頻度の高いコードが先頭にあるため線形探索でも平均探索回数が少なく済みます。
• cはコードから格納位置が一定に決まるため、ハッシュ表探索が最適で直接アクセスが可能です。
  これらの理由から、選択肢ア（a：2分探索、b：線形探索、c：ハッシュ表探索）が正解です。

よくある誤解

• 「整列されていれば線形探索でも十分」と考えがちですが、2分探索の方が効率的です。
• 使用頻度順の探索表に2分探索を適用すると、頻度の高い要素を活かせず非効率になります。

解法ステップ

1. 各探索表の構成を確認し、整列状態や格納規則を把握する。
2. 整列済みなら2分探索、整列されていなければ線形探索やハッシュ探索を検討。
3. 使用頻度順なら線形探索が有効か判断。
4. コードから位置が決まる場合はハッシュ表探索を選択。
5. 各探索手法の特徴と探索表の構造を照合し、最適な組合せを選ぶ。

選択肢別の誤答解説

• イ：bにハッシュ表探索を選んでいるが、bは使用頻度順でハッシュ表は不適切。
• ウ：aに線形探索を選んでいるが、aは整列済みで2分探索が効率的。
• エ：cに2分探索を選んでいるが、cはコードから位置が決まるためハッシュ表探索が適切。

補足コラム

• 2分探索は整列済み配列に対して$O(\log n)$の探索時間を持ち、効率的です。
• 線形探索は整列されていない場合や使用頻度順のように先頭にヒットしやすい場合に有効です。
• ハッシュ表探索はハッシュ関数によりコードから直接格納位置を計算し、平均$O(1)$の高速アクセスを実現します。

FAQ