探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。

選択肢

• アア：a=2分探索，b=線形探索，c=ハッシュ表探索
• イイ：a=2分探索，b=ハッシュ表探索，c=線形探索
• ウウ：a=線形探索，b=2分探索，c=ハッシュ表探索
• エエ：a=線形探索，b=ハッシュ表探索，c=2分探索

正解と解説

正解：ア ア：a=2分探索，b=線形探索，c=ハッシュ表探索

探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。

選択肢ごとの解説

• ア正しい。整列済みは2分探索、頻度順は線形探索、計算位置格納はハッシュ表探索となる。
• イ頻度順の表にハッシュ表探索は適さず、飛び飛び配置に線形探索も非効率。
• ウ整列済みの表に線形探索を当てはめており、2分探索の利点を活かせない。
• エ整列済みに線形探索、飛び飛び配置に2分探索としており、いずれも不適切。

この問題に出た用語

• ハッシュ表（連想配列）
• 2分探索
• 線形探索

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 午前 問6
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 午前 問6
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 午前 問19
• 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における…2023年度 春期 午前 問6
• 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力…2018年度 秋期 午前 問27