平成30年度 秋期 応用情報技術者試験 問8

解説

正解は1です。 この問題は、データの並べ方が異なる3種類の探索表に、それぞれ最も適した探索手法を対応付けるものです。 図のaでは、コードが120380、120381、120520、140140と昇順に詰めて並んでいます。 bでは、120381、140140、120520、120380と、コードの大小とは無関係な順（使用頻度順）に並んでいます。 cでは、表の途中に空欄があり、各コードが飛び飛びの位置に格納されています。 【a〜cの検討】 a：コード順に整列しているので、中央の要素と比べて探索範囲を半分ずつ絞り込む2分探索が使えます。 b：コード順ではないため2分探索は使えません。 使用頻度の高いものが先頭にあるので、先頭から順に調べる線形探索なら、よく使うコードほど早く見つかります。 c：コードから計算で格納位置が一意に決まるので、ハッシュ関数で位置を求めて直接参照するハッシュ表探索が適しています。 【選択肢別解説】 1：○ a：2分探索、b：線形探索、c：ハッシュ表探索で、上の検討と全て一致します。 2：× bにハッシュ表探索、cに線形探索を割り当てています。 bは格納位置がコードから決まらないのでハッシュ表探索はできません。 cは位置を計算で求められるので、空欄を含めて順に調べる線形探索より、ハッシュ表探索が適しています。 3：× aに線形探索、bに2分探索を割り当てています。 2分探索は整列済みの表が前提なので、使用頻度順のbには使えません。 整列済みのaこそ2分探索に向いています。 4：× cに2分探索を割り当てていますが、cはコード順に並んでいないので2分探索は使えません。 bへのハッシュ表探索も、位置がコードから決まらないため成り立ちません。 【ポイント】 2分探索は整列済みであることが前提で、n件の表をおよそlog_2n回の比較で探索できます。 線形探索は並び順を問いませんが、平均でn／2回程度の比較が必要です。 ハッシュ表探索は、衝突がなければ1回の計算で格納位置が決まります。