応用情報アルゴリズムとプログラミング 2

Question 1

マージソートの時間計算量（最悪・平均・最良）の組合せとして正しいものはどれか？

Accepted Answer

すべてO(n log n)

Answer

マージソートは分割統治法を用い、常に均等に分割するため最悪・平均・最良のすべてでO(n log n)の安定した性能を持つ。

Question 2

木構造において、根（ルート）から最も遠い葉までの距離を表す用語はどれか？

Accepted Answer

高さ（height）

Answer

木の高さは根から最も遠い葉ノードまでの辺の数で定義され、木構造の縦方向の大きさを表す。

Question 3

深さ優先探索（DFS）の実装に主に使われるデータ構造はどれか？

Accepted Answer

スタック

Answer

DFSはスタック（または再帰呼び出し）を使って実装し、一方向に深く進んでからバックトラックして別の経路を探索する。

Question 4

幅優先探索（BFS）の実装に主に使われるデータ構造はどれか？

Accepted Answer

キュー

Answer

BFSはキューを使って実装し、根に近いノードから順に探索することで最短経路を見つけることができる。

Question 5

線形探索の平均時間計算量はどれか？

Accepted Answer

O(n)

Answer

線形探索はデータを先頭から順番に比較するため、平均してn/2回の比較が必要となりO(n)となる。

応用情報技術者練習テスト