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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

0 から k の範囲の n 個の整数に対する計数ソート（counting sort）の実行時間は何ですか？

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

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

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

標準的な配列ベースのマージソートは、どれだけの追加メモリを使いますか？

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

漸化式 T(n) = 2T(n/2) + O(n) の解はどれですか？

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

活動選択問題で、重ならない活動の数を常に最大にする貪欲な規則はどれですか？

  1. A重なりの最も少ない活動を先に選び、両立する活動で繰り返す
  2. B最も早く始まる活動を選ぶ
  3. C最も短い活動から選ぶ
  4. D最も早く終わる活動を選び、両立する活動で繰り返す
6.ふつう

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

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

V 個の頂点と E 本の辺をもつグラフで、二分ヒープを用いたダイクストラ法の実行時間は何ですか？

  1. AO(V + E)
  2. BO((V + E) log V)
  3. CO(V³)
  4. DO(V × E)
8.むずかしい

停止問題（halting problem）が示していることはどれですか？

  1. Aすべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない
  2. B一部のプログラムは高速なコンピュータでより速く動作するので、停止するかどうかはハードウェアに依存するから
  3. Cループは避けるべきである
  4. Dすべてのプログラムはいずれ停止する

解答

  1. 1. B · O(n + k)
  2. 2. A · O(n log n)
  3. 3. B · O(n)
  4. 4. C · O(n log n)
  5. 5. D · 最も早く終わる活動を選び、両立する活動で繰り返す
  6. 6. B · O(2ⁿ)
  7. 7. B · O((V + E) log V)
  8. 8. A · すべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない

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