平成30年度 秋期 午前 問8

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

解説

並び方が決まれば使える探索法も1つに決まります。

三通りの並べ方をした探索表それぞれに、最も適した探索手法を当てはめる問いです。手掛かりは表の並び方だけで、並び方が決まれば使える手法は一つに決まります。一つ目はコードが昇順に詰めて並んでいます。真ん中と比べれば探す値がどちら側にあるか分かり、そのたびに残りを半分ずつ捨てられます。二つ目はコードの使用頻度の順に並んでいて、コードの大小はばらばらです。大小の手掛かりがないので真ん中と比べても何も捨てられず、先頭から順に見ていく線形探索になります。ただしよく使うコードほど前にあるので、平均の比較回数は小さくて済みます。三つ目は空き行が飛び飛びに残っています。詰めて置いていないということは、順番にも頻度にも意味がないということです。置き場所はコードから計算して決めていますから、ハッシュ表探索です。三つとも決まれば、組合せも一つに定まります。見分けの軸は、表の姿から逆に手法をたどることです。きっちり詰まって昇順なら半分ずつ捨てられ、詰まっているが順序に意味がなければ先頭から見るしかなく、空きが散らばっていれば計算で場所を出しています。平均の比較回数も、計算で決まるものがほぼ一回、半分ずつ捨てるものが対数の程度、先頭から見るものが件数の半分と、この順に並びます。

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

• イa … 2 分探索／b … ハッシュ表探…：使用頻度順の表を計算で場所を決める方式としています。しかしその方式では置き場所がコードから一意に決まってしまうので、頻度に合わせて並べ替える余地がありません。空きが飛び飛びに残った三つ目の表の姿も説明できなくなります。
• ウa … 線形探索／b … 2 分探索／c…：昇順に詰まった表を先頭から順に見る方式としています。せっかく大小の順に並んでいるという手掛かりを捨てることになりますし、使用頻度順の表を半分ずつ捨てる方式にするのも、大小の順になっていない以上は成り立ちません。
• エa … 線形探索／b … ハッシュ表探索…：空き行が飛び飛びに残った表を半分ずつ捨てる方式としています。詰めて置いていない以上、大小の順に並んでいる保証がなく、真ん中と比べる手が使えません。昇順の表と頻度順の表の当て方も入れ替わっています。