応用情報 アルゴリズムとプログラミング 2 — Questions and Answers
Question 1: マージソートの時間計算量（最悪・平均・最良）の組合せとして正しいものはどれか？
- すべてO(n²)
- すべてO(n log n) (Correct answer)
- 平均O(n log n)・最悪O(n²)
- すべてO(n)
Correct answer: すべてO(n log n)
マージソートは分割統治法を用い、常に均等に分割するため最悪・平均・最良のすべてでO(n log n)の安定した性能を持つ。
Question 2: 木構造において、根（ルート）から最も遠い葉までの距離を表す用語はどれか？
- 次数（degree）
- 高さ（height） (Correct answer)
- 幅（width）
- 直径（diameter）
Correct answer: 高さ（height）
木の高さは根から最も遠い葉ノードまでの辺の数で定義され、木構造の縦方向の大きさを表す。
Question 3: 深さ優先探索（DFS）の実装に主に使われるデータ構造はどれか？
- キュー
- スタック (Correct answer)
- ヒープ
- 優先度付きキュー
Correct answer: スタック
DFSはスタック（または再帰呼び出し）を使って実装し、一方向に深く進んでからバックトラックして別の経路を探索する。
Question 4: 幅優先探索（BFS）の実装に主に使われるデータ構造はどれか？
- スタック
- キュー (Correct answer)
- 二分ヒープ
- 連結リスト
Correct answer: キュー
BFSはキューを使って実装し、根に近いノードから順に探索することで最短経路を見つけることができる。
Question 5: 線形探索の平均時間計算量はどれか？
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n²)
Correct answer: O(n)
線形探索はデータを先頭から順番に比較するため、平均してn/2回の比較が必要となりO(n)となる。
Question 6: 動的計画法（Dynamic Programming）の主な特徴として正しいものはどれか？
- 問題を独立した小問題に分割してそれぞれを解く
- 重複する部分問題の解をメモ化して再利用する (Correct answer)
- 乱数を用いて最適解に近い解を求める
- 常にO(n log n)の時間計算量を保証する
Correct answer: 重複する部分問題の解をメモ化して再利用する
動的計画法は重複する部分問題の解をメモ化（テーブルに保存）して再利用することで、同じ計算を繰り返さず効率的に解く手法である。
Question 7: 選択ソートの動作として正しいものはどれか？
- 隣接する要素を比較して必要に応じて交換する操作を繰り返す
- 未整列部分から最小値（または最大値）を選び整列済み部分の末尾に移動する (Correct answer)
- 整列済み部分に新しい要素を適切な位置に挿入する操作を繰り返す
- ピボットを基準に要素を分割して再帰的にソートする
Correct answer: 未整列部分から最小値（または最大値）を選び整列済み部分の末尾に移動する
選択ソートは未整列部分から最小値を探して先頭の要素と交換する操作を繰り返すアルゴリズムで、時間計算量はO(n²)である。
応用情報 アルゴリズムとプログラミング 2
マージソートの時間計算量（最悪・平均・最良）の組合せとして正しいものはどれか？