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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V²)
  4. DO(V + E)
2.やさしい

マージソートの最悪時間計算量は何ですか？

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

メモ化（memoisation）とは何ですか？

  1. A関数が戻った後にメモリを解放すること
  2. B再帰を自動的に等価なループに変換し、コールスタックを不要にすること
  3. C関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  4. Dコードの各行の横にコメントを書くこと
4.ふつう

動的計画法がマージソートを実質的に高速化しないのはなぜですか？

  1. A部分問題が重複しないので、再利用するものがないから
  2. Bマージソートには再帰的な構造がないから
  3. C動的計画法はグラフ問題にしか使えず、配列には使えないから
  4. Dマージソートはすでに O(n) だから
5.ふつう

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(n)
  4. DO(2ⁿ)
6.ふつう

比較に基づくソートの最悪の場合の下界はどれですか？

  1. AΩ(n)
  2. BΩ(n log n)
  3. CΩ(n²)
  4. DΩ(log n)
7.むずかしい

トポロジカルソートが可能なのは、次のどのグラフだけですか？

  1. A負の重みを持つグラフ
  2. B完全グラフ
  3. C無向グラフ
  4. D有向非巡回グラフ（DAG）
8.むずかしい

ベルマン－フォード法は、始点から到達可能な負の重みの閉路をどのように検出しますか？

  1. AV − 1 回のラウンドの後、まだ緩和できる辺があるかどうかを調べる
  2. Bダイクストラ法を 2 回実行し、2 つの距離の結果を比べる
  3. C負の重みをもつ辺があるかどうかを調べる
  4. D深さ優先探索で閉路を数える

解答

  1. 1. D · O(V + E)
  2. 2. B · O(n log n)
  3. 3. C · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  4. 4. A · 部分問題が重複しないので、再利用するものがないから
  5. 5. D · O(2ⁿ)
  6. 6. B · Ω(n log n)
  7. 7. D · 有向非巡回グラフ（DAG）
  8. 8. A · V − 1 回のラウンドの後、まだ緩和できる辺があるかどうかを調べる

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