平成25年度 春期 午前 問5

✓ これが正解アa＝2 分探索 ／ b＝線形探索 ／ c＝ハッシュ表探索

解説

並びの性質から使える探索手法がそれぞれ決まります。

三つの表は格納の仕方が違うだけですので、それぞれの並びから何が言えるかを順に考えます。昇順に詰めて並んでいる表なら、真ん中と比べて範囲を半分に絞り込めますから、2 分探索が最も速く当たります。使用頻度の順に並んだ表は、コードの大小と並びが無関係ですので、絞り込みの手がかりがありません。上から順に見ていく線形探索しか成り立ちません。コードから格納位置が直に決まり、間に空きが残る表は、ハッシュ表の姿そのものです。コードを関数に通して位置を求めますから、衝突を考えなければ一回で当たります。設問が表の空きにわざわざ触れているのが伏線で、空きが飛び飛びに残るのは詰めて格納しない方式の特徴です。三つを順に決めれば組合せは一つに定まります。並びが整っているかどうかを最初に見る、というのがこの型の解き方です。

ほかの選択肢はなぜ違うのか

• イa＝2 分探索 ／ b＝ハッシュ表探索 …：頻度順の表に位置を計算で求める手法を当て、空きが飛び飛びに残る表を上から順に見る形にしています。どちらも格納の仕方と噛み合いません。
• ウa＝線形探索 ／ b＝2 分探索 ／ c…：昇順に詰まった表と頻度順の表を入れ替えた形です。頻度順の並びでは大小による絞り込みができませんので、範囲を半分ずつ狭める手法を当てることはできません。
• エa＝線形探索 ／ b＝ハッシュ表探索 ／…：空きが飛び飛びに残る表に、順に詰まっていることを前提とする手法を当てています。中央と比べる手順が成り立ちませんし、頻度順の表の扱いも位置の計算とは結び付きません。