応用情報技術者試験 平成30年秋 午前問8 解説付き過去問
問題
探索表の構成法を例とともに a～c に示す。
最も適した探索手法の組合せはどれか。
ここで、探索表のコードの空欄は表の空きを示す。
正解
解説
この問題は、異なるデータ構造における最も効率的な探索手法を選択することを要求しています。それぞれの探索表の特性に基づいて、最も適した探索手法を選ぶ必要があります。
- ２分探索の適用
２分探索は、事前にソートされたデータに対して非常に効率的です。画像の中の表aはソートされており、中間の値から探索を開始し、探索範囲を半分に減らすことができるため、２分探索が適しています。 - 線形探索の適用
線形探索は、特に事前のソートやデータ構造に依存しない探索方法です。表bに示されたように、データがランダムまたは無秩序である場合、最も簡単で直接的な方法は線形探索です。各要素を順に調べることで目的のデータを見つけることができます。 - ハッシュ表探索の適用
ハッシュ表探索は、キーに基づいて直接アクセスが可能なため高速です。表cのように、空きを含む可能性がある場合でも、ハッシュ関数を使用してデータの位置を直接決定し探索時間を大幅に短縮することができます。
したがって、a：２分探索、b：線形探索、c：ハッシュ表探索の組み合わせは、それぞれのデータ構造に最適な探索方法を適用しており、この選択が正解です。