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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

増加の上界（upper bound）を表す記法はどれですか？

  1. ABig Omega
  2. BLittle omega
  3. CBig O
  4. DBig Theta
3.やさしい

log₂ 1024 はいくつですか？

  1. A512
  2. B10
  3. C12
  4. D32
4.ふつう

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

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

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

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

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

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

決定問題 X が NP 完全であることを証明するには、どの 2 つのことを示さなければなりませんか？

  1. AX に多項式アルゴリズムがないこと、および X が決定可能であること
  2. BX が P の問題に帰着すること、および X が NP に属すること
  3. CX が P に属すること、および X が SAT に帰着すること
  4. DX が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること
8.むずかしい

クラス P の定義として正しいものはどれですか？

  1. A決定性アルゴリズムによって多項式時間で解ける決定問題
  2. Bどのコンピュータでも指数時間を必要とする問題
  3. C解を多項式時間で検証できるが、見つけることは決してできない問題
  4. D並列に解くことができる問題

解答

  1. 1. D · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  2. 2. C · Big O
  3. 3. B · 10
  4. 4. B · 部分問題が重複しないので、再利用するものがないから
  5. 5. B · O(n²)
  6. 6. A · O(n)
  7. 7. D · X が NP に属すること、および既知の NP 完全問題が多項式時間で X に帰着すること
  8. 8. A · 決定性アルゴリズムによって多項式時間で解ける決定問題

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