平成22年度秋期 システムアーキテクト 午前Ⅰ 問3

探索表の構成と効率を考える視点

構成の違いが、探索時に必要となる確認の範囲や比較の進み方へどう影響するかを、個別の選択肢ではなく全体の仕組みとして捉え、規模や条件の変化にも注目して整理しましょう。

この問題で問われていること

この設問では、探索表をどのように組み立てるかという観点と、探索にかかる手間を評価する観点を分け、両者のつながりを説明できるか、また前提条件を取り違えていないかに焦点を当てます。

視点

探索表を学ぶときは、データの並び方、参照の起点、候補を絞る過程、規模が変わったときの負担を切り分けて考えると、構成と効率の関係を整理しやすくなります。

確認ポイント

• データの並び方と参照の進み方を分けて確認する
• 対象の規模が変化した場合の負担に注目する
• 構成上の前提と効率の評価基準を整理する

正解

ア

解説

aはコード順なので大小比較で範囲を絞る2分探索、bは使用頻度順なので先頭から調べる線形探索、cはコードから位置が一意に定まるのでハッシュ表探索を用いる。したがって組合せはアです。

理由

aの表はコードの昇順に格納されているため、中央付近の値との大小を比較し、探索範囲を半分ずつ絞り込める2分探索が適している。bは使用頻度の高いコードから並ぶため、よく使うデータほど先に見つけやすい線形探索が適している。

比較

cはコードから格納場所が一意に決まるため、ハッシュ関数などで位置を求めて直接探索できるハッシュ表探索が適している。よってa・b・cの組合せは、それぞれ2分探索・線形探索・ハッシュ表探索となる。

選択肢ア（正解）

これは正解だよ。aはコード順に並んでいるので、大小比較で探索範囲を絞る2分探索が適する。bは使用頻度順なので、先頭から調べる線形探索が適する。cはコードから格納位置が一意に決まるため、ハッシュ表探索が適し、この組合せが表の構成と一致する。

選択肢イ

これは不正解だよ。aのコード順に対する2分探索は正しいが、bの使用頻度順の表にハッシュ表探索を対応させている点が誤りである。使用頻度順はコードから位置を直接決める構成ではないため、ハッシュ表探索の前提を満たさず、cの線形探索も表の特徴と一致しない。

選択肢ウ

これは不正解だよ。bの使用頻度順に対する2分探索は、コードの大小順に並んでいないため探索範囲を半分に絞れず、適切ではない。aはコード順なので線形探索より2分探索が適し、cはコードから位置が決まるためハッシュ表探索を用いる。

選択肢エ

これは不正解だよ。aのコード順の表を線形探索とする点、cのコードから一意に決まる表を2分探索とする点が、それぞれ表の特徴と合わない。コード順には2分探索、直接位置が決まる構成にはハッシュ表探索を対応させる必要がある。

学習のポイント

表の並び方と探索アルゴリズムの前提を対応付けることが重要です。