解答つきアルゴリズムと計算量ワークシート

無料で印刷できるアルゴリズムと計算量のワークシート：やさしい問題から試験レベルまで 8 問、解答つき。印刷するか PDF で保存できます。

新しいワークシートヒントつきでオンライン練習

先生方へ： 授業で自由に印刷・コピーしてお使いいただけます。新しいワークシートごとに数値が変わり、専用の解答が付きます。授業ページに ExamProblems へのリンクを載せていただけると嬉しいです。

名前: ____________________   日付: ____________

1.やさしい

n 個の数からなる未ソートの配列で最大値を見つける時間計算量は何ですか？

  1. AO(n)
  2. BO(n log n)
  3. CO(1)
  4. DO(log n)
2.やさしい

挿入ソート（insertion sort）の最悪時間計算量は何ですか？

  1. AO(n²)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
3.やさしい

隣接リストで格納されたグラフに対する深さ優先探索の時間計算量は何ですか？

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V²)
  4. DO(V + E)
4.ふつう

到達可能な基底部をもたない再帰関数について、正しい記述はどれですか？

  1. Aコンパイラが常にそれを、安全に終了するループに変換する
  2. BO(1) 時間で動作する
  3. Cコールスタックがオーバーフローするまで自分自身を呼び続ける
  4. D自動的に 0 を返す
5.ふつう

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

  1. Aすべてのグラフにおけるトポロジカル順序
  2. B始点ノードからの辺の数で測った最短経路
  3. C負の辺の重みを含むグラフでの最短経路
  4. D最小全域木
6.ふつう

漸化式 T(n) = T(n − 1) + O(n) の解は何ですか？

  1. AO(2ⁿ)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
7.むずかしい

次の充足可能性問題のうち、多項式時間で解けることが知られているのはどれですか？

  1. A回路充足可能性問題
  2. B各節のリテラルが高々 2 個の 2-SAT
  3. C連言標準形の式に対する一般の SAT
  4. D各節のリテラルがちょうど 3 個の 3-SAT
8.むずかしい

決定不能な問題と扱いにくい問題の違いは何ですか？

  1. A決定不能な問題にはすべての入力で解くアルゴリズムがなく、扱いにくい問題にはあるが遅すぎる
  2. B扱いにくい問題はどのアルゴリズムでも解けず、決定不能な問題は指数時間を必要とするだけである
  3. Cどちらもアルゴリズムがまったくないことを意味する
  4. D決定不能な問題は NP に属し、扱いにくい問題は P に属する

解答

  1. 1. A · O(n)
  2. 2. A · O(n²)
  3. 3. D · O(V + E)
  4. 4. C · コールスタックがオーバーフローするまで自分自身を呼び続ける
  5. 5. B · 始点ノードからの辺の数で測った最短経路
  6. 6. C · O(n²)
  7. 7. B · 各節のリテラルが高々 2 個の 2-SAT
  8. 8. A · 決定不能な問題にはすべての入力で解くアルゴリズムがなく、扱いにくい問題にはあるが遅すぎる

ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。