線形探索・二分探索・ハッシュ探索・グラフ探索を10問で比較します。各問を解いてから解説を開き、前提と計算量を確認しましょう。学習用のオリジナル問題です。
解く前の確認
配列が整列済みか、キーに重複があるか、グラフに重みがあるかで使える方法が変わります。計算量の増え方と、実装を指定した厳密な比較回数は区別します。
第1問
昇順に整列済みの配列に対して、探索対象を高速に見つけるアルゴリズムはどれか。
A. 線形探索
B. 二分探索
C. 深さ優先探索
D. 幅優先探索
第1問の解答・解説を見る
正解：B
解説
二分探索は整列済みデータに対して高速探索を行う代表的手法。
第2問
配列A[0..1023]に1〜1024が昇順に入っている。lo＝0、hi＝1023から始め、mid＝⌊(lo＋hi)/2⌋で中央を調べ、目的値より小さければlo＝mid＋1、大きければhi＝mid−1とする。1024が見つかるまで中央要素を調べる回数は何回か。中央要素との大小判定一組を1回と数える。
A. 10回
B. 11回
C. 32回
D. 512回
第2問の解答・解説を見る
正解：B（11回）。調べる値は512、768、896、960、992、1008、1016、1020、1022、1023、1024です。log₂1024＝10は増え方の目安で、実装を指定した成功時の最大確認回数が必ず10回になるわけではありません。
第3問
二分探索について、適切な説明はどれか。
A. データは整列不要である
B. 探索範囲を半分ずつ狭める
C. 必ず先頭から順番に探索する
D. 木構造専用の探索方式である
第3問の解答・解説を見る
正解：B
解説
二分探索は中央要素を確認し、探索範囲を半分に絞る。
第4問
深さ優先探索（DFS）で主に使用されるデータ構造はどれか。
A. 配列
B. キュー
C. スタック
D. ハッシュ表
第4問の解答・解説を見る
正解：C。DFSはスタックで次に調べる頂点を管理できます。再帰実装では呼出しスタックを使います。配列はスタックを実装する手段にもなるため、ここでは抽象的な管理方式を問うています。
第5問
幅優先探索（BFS）で主に使用されるデータ構造はどれか。
A. スタック
B. キュー
C. 木構造
D. 配列
第5問の解答・解説を見る
正解：B。BFSはFIFOのキューで、先に発見した頂点から順に処理します。配列などでキューを実装することもできます。
第6問
n個の異なる要素のどれもが等確率で探索対象となる成功探索で、線形探索の平均時間計算量として最も適切なものはどれか。
A. O(1)
B. O(log n)
C. O(n)
D. O(n2)
第6問の解答・解説を見る
正解：C。平均確認数は(n＋1)/2で、nに比例して増えます。先頭で見つかる最良時はO(1)、最悪時はO(n)です。
第7問
ハッシュ探索の特徴として適切なものはどれか。
A. 必ずデータを整列する必要がある
B. 平均的には高速に探索できる
C. 木構造でしか利用できない
D. 必ず線形探索より遅い
第7問の解答・解説を見る
正解：B。適切なハッシュ関数と負荷率・衝突処理の条件では平均O(1)が期待できますが、衝突が集中するなど最悪時にはO(n)になり得ます。
第8問
ハッシュ法において、異なるキーが同じ格納位置になる現象を何というか。
A. マージ
B. ソート
C. コリジョン
D. スワップ
第8問の解答・解説を見る
正解：C
解説
異なるキーが同じ位置になる現象をコリジョン（衝突）という。
第9問
キーに重複のない二分探索木において、各節点について成り立つ条件として適切なものはどれか。
A. 左部分木 ＞ 親 ＞ 右部分木
B. 左部分木 ＜ 親 ＜ 右部分木
C. 左部分木 ＝ 親 ＝ 右部分木
D. 左右どちらも大小関係はない
第9問の解答・解説を見る
正解：B。各節点について、左部分木の全キーはその節点より小さく、右部分木の全キーは大きくなります。直下の子だけの大小関係では不十分です。重複キーの扱いは別途規則が必要です。
第10問
重みのないグラフで、始点から辺の本数が少ない頂点から順に調べ、最少辺数の経路を求められる方法はどれか。
A. 線形探索
B. 二分探索
C. 深さ優先探索
D. 幅優先探索
第10問の解答・解説を見る
正解：D。BFSは距離を辺の本数として層ごとに探索します。辺ごとに異なる重みがある最短経路へ、そのまま一般化はできません。閉路のあるグラフでは訪問済み管理も必要です。
間違えた分野から復習する
第1〜3・6問は配列探索、第4・5・10問はグラフ探索、第7・8問はハッシュ、第9問は木の条件を確認しましょう。
線形・二分探索やハッシュの計算量を整理したい方は、対応するnote教材へ進めます。グラフ探索専用の解説としてではなく、処理量の基礎を補う教材です。
コメント