実践問題
解答＆解説は第1問から第10問までを列挙しています。
まず問題を解いてから解答&解説を見ることを推奨します。
第1問
昇順に整列済みの配列に対して、探索対象を高速に見つけるアルゴリズムはどれか。
A. 線形探索
B. 二分探索
C. 深さ優先探索
D. 幅優先探索
解答＆解説はこちら
第2問
要素数1024の整列済み配列に対して二分探索を行う。
目的データが存在するとき、最大比較回数はおよそ何回か。
A. 10回
B. 32回
C. 100回
D. 512回
解答＆解説はこちら
第3問
二分探索について、適切な説明はどれか。
A. データは整列不要である
B. 探索範囲を半分ずつ狭める
C. 必ず先頭から順番に探索する
D. 木構造専用の探索方式である
解答＆解説はこちら
第4問
深さ優先探索（DFS）で主に使用されるデータ構造はどれか。
A. 配列
B. キュー
C. スタック
D. ハッシュ表
解答＆解説はこちら
第5問
幅優先探索（BFS）で主に使用されるデータ構造はどれか。
A. スタック
B. キュー
C. 木構造
D. 配列
解答＆解説はこちら
第6問
線形探索の平均計算量として最も適切なものはどれか。
A. O(1)
B. O(log n)
C. O(n)
D. O(n2)
解答＆解説はこちら
第7問
ハッシュ探索の特徴として適切なものはどれか。
A. 必ずデータを整列する必要がある
B. 平均的には高速に探索できる
C. 木構造でしか利用できない
D. 必ず線形探索より遅い
解答＆解説はこちら
第8問
ハッシュ法において、異なるキーが同じ格納位置になる現象を何というか。
A. マージ
B. ソート
C. コリジョン
D. スワップ
解答＆解説はこちら
第9問
二分探索木において、各節点について成り立つ条件として適切なものはどれか。
A. 左部分木 ＞ 親 ＞ 右部分木
B. 左部分木 ＜ 親 ＜ 右部分木
C. 左部分木 ＝ 親 ＝ 右部分木
D. 左右どちらも大小関係はない
解答＆解説はこちら
第10問
次の特徴をもつ探索方式はどれか。
- 近いノードから順番に探索する
- 最短経路問題で利用されやすい
A. 線形探索
B. 二分探索
C. 深さ優先探索
D. 幅優先探索
解答＆解説はこちら
解答&解説
解答：第1問
正解：B
解説
二分探索は整列済みデータに対して高速探索を行う代表的手法。
解答：第2問
正解：A
解説
二分探索の最大比較回数：
log2 1024 = 10
よって約10回。
解答：第3問
正解：B
解説
二分探索は中央要素を確認し、探索範囲を半分に絞る。
解答：第4問
正解：C
解説
DFSは「後入れ先出し」のスタックを利用する。
解答：第5問
正解：B
解説
BFSは「先入れ先出し」のキューを利用する。
解答：第6問
正解：C
解説
線形探索は最悪・平均ともにデータ数に比例する。
解答：第7問
正解：B
解説
ハッシュ探索は平均的には非常に高速で、
O(1)
程度で探索可能。
解答：第8問
正解：C
解説
異なるキーが同じ位置になる現象をコリジョン（衝突）という。
解答：第9問
正解：B
解説
二分探索木は
左部分木< 親 < 右部分木
の関係を満たす。
解答：第10問
正解：D
解説
幅優先探索（BFS）は近いノードから順番に探索するため、最短経路問題でも利用される。
コメント