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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

  1. A解がない場合
  2. B多項式時間で解ける場合
  3. Cあらゆる可能性を試すことでしか解けない場合
  4. D定数時間で解ける場合
2.やさしい

log₂ 1024 はいくつですか？

  1. A32
  2. B10
  3. C512
  4. D12
3.やさしい

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

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

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

  1. AKruskal 法
  2. B深さ優先探索（DFS）
  3. CDijkstra 法
  4. Dどの場合でも Bellman–Ford が必要
5.ふつう

for i = 1 to n: for j = 1 to i: do O(1) work の時間計算量は何ですか？

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

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

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

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

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

挿入ソートはソート済みの入力に対して O(n) で動作します。これは比較ソートの Ω(n log n) の下界と矛盾しますか？

  1. Aはい。ただし 100 より短い配列の場合に限る
  2. Bいいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
  3. Cいいえ。挿入ソートは比較ソートではないから
  4. Dはい。したがって下界は誤りである

解答

  1. 1. B · 多項式時間で解ける場合
  2. 2. B · 10
  3. 3. C · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  4. 4. C · Dijkstra 法
  5. 5. A · O(n²)
  6. 6. A · O(n)
  7. 7. C · 品物を分割できる分数ナップサック問題
  8. 8. B · いいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない

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