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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

log₂ 1024 はいくつですか？

  1. A32
  2. B512
  3. C10
  4. D12
2.やさしい

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

  1. ABig O
  2. BBig Omega
  3. CBig Theta
  4. DLittle omega
3.やさしい

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

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

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

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

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

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

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

  1. A貪欲法は 2 枚、最適解は 2 枚
  2. B貪欲法は 3 枚、最適解は 2 枚
  3. C貪欲法は 3 枚、最適解は 3 枚
  4. D貪欲法は 4 枚、最適解は 3 枚
7.むずかしい

クック－レビンの定理は何を確立しましたか？

  1. Aすべての NP 問題が指数時間で解けること
  2. B停止問題が決定不能であること
  3. Cブール充足可能性問題（SAT）が NP 完全であること
  4. DP が NP と等しくないこと
8.むずかしい

ナップサック問題のどの変種で、「重さあたりの価値の順に品物をとる」という貪欲な規則が常に最適解を与えますか？

  1. A品物を分割できる分数ナップサック問題
  2. B両方の変種
  3. C品物を必ず丸ごととらなければならない 0/1 ナップサック問題
  4. Dどちらの変種でもない

解答

  1. 1. C · 10
  2. 2. A · Big O
  3. 3. C · O(n)
  4. 4. A · O(2ⁿ)
  5. 5. D · O(n²)
  6. 6. B · 貪欲法は 3 枚、最適解は 2 枚
  7. 7. C · ブール充足可能性問題（SAT）が NP 完全であること
  8. 8. A · 品物を分割できる分数ナップサック問題

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