平成22年度 秋期 午前 問6

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

解説

格納の並び方が、使える探索手法を先に決めます。

まず設問の読み方を確かめます。問われているのは 3 つの表それぞれについて平均計算量が最も小さくなる手法であって、3 つの中でいちばん速い表を 1 つ選ぶ問いではありません。決め手は、その表の並び方が何を許すかです。コード順に詰めて並んでいる表は、大小を比べて範囲を半分ずつ絞れるので 2 分探索が効きます。使用頻度の順に並んでいる表は、並びがコードの大小と無関係なので絞り込みの手がかりがなく、上から順に見る線形探索しかありません。頻度の高いものが上にある分だけ平均は小さくなりますが、手法としては順に見る側です。コードから格納する場所が一意に決まり、間に空きが残る表は、位置を計算で求めるハッシュ表探索の姿です。設問がわざわざ、コードの空欄は表の空きを示す、と断っているのが伏線で、空きが飛び飛びに残るのは詰めて格納しない方式の特徴です。この 3 つを並べた組合せが正解になります。

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

• イa＝2 分探索 ／ b＝ハッシュ表探索 …：格納の場所が計算で一意に決まる表に、上から順に見る手法を当てています。位置が直に求まるのに全体を走査するのでは、その並べ方の利点を捨てることになります。
• ウa＝線形探索 ／ b＝2 分探索 ／ c…：コード順に詰めた表と、使用頻度順に並べた表の割り当てが入れ替わっています。大小で範囲を絞れるのは前者だけで、後者には絞り込みの手がかりがありません。
• エa＝線形探索 ／ b＝ハッシュ表探索 ／…：間に空きが残る表に、範囲を半分ずつ絞る手法を当てています。この手法は値が順に詰まっていることを前提にするので成り立たず、コード順の表も順に見る側にしています。