修了試験 2021-07-25実施分 基本情報技術者試験 問9

解説

正解は1です。 探索表の並び方に応じて、適した探索手法が異なります。 整列されているか、よく使うものが先頭にあるか、コードから格納位置が計算できるかで判断します。 【探索表ごとの考え方】 a：コード順に整列した表は、中央の値と比べて探索範囲を半分ずつ絞り込む2分探索に適しています。 b：使用頻度順の表はコード順に並んでいないので2分探索は使えません。 先頭から順に調べる線形探索を使えば、よく使うコードほど早く見つかります。 c：コードから一意に決まる場所に格納した表は、ハッシュ関数で格納位置を計算するハッシュ表探索に適しています。 【選択肢別解説】 1：○ a：2分探索、b：線形探索、c：ハッシュ表探索で、すべての組合せが適切です。 2：× bにハッシュ表探索、cに線形探索を割り当てています。 bは格納位置が計算で決まらず、cは位置を計算できるのに順に探すのは非効率です。 3：× aに線形探索、bに2分探索を割り当てています。 bは整列していないので2分探索は使えません。 4：× cに2分探索を割り当てています。 cは空きをはさんでコードが散らばっており、整列された表ではないので2分探索は使えません。 【ポイント】 2分探索は「整列済み」が前提、線形探索は「並びを問わない」、ハッシュ表探索は「計算で位置を決める」が特徴です。 使用頻度順に並べた線形探索は、よく使うデータを短時間で見つけられます。