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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

O(2ⁿ) の増加は何と呼ばれますか？

  1. A対数的
  2. B線形
  3. C指数的
  4. D多項式的
2.やさしい

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

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

f(n) = Θ(g(n)) はどういう意味ですか？

  1. Aすべての n について f は常に g より小さいので、g は上からは抑えるが下からは決して抑えない
  2. Bf は g より真に速く増加する
  3. Cf は g より真に遅く増加する
  4. Df は g と同じ速さで増加し、上下から g の定数倍で抑えられる
4.ふつう

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

  1. AΩ(n log n)
  2. BΩ(n)
  3. CΩ(log n)
  4. DΩ(n²)
5.ふつう

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

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

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

  1. A計算機科学のすべての対数は底が 10 なので、省略されているから
  2. B対数は常に整数に丸められるから
  3. C底は n が小さいときにしか問題にならないから
  4. D底の異なる対数は定数倍しか違わないから
7.むずかしい

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

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

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

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

解答

  1. 1. C · 指数的
  2. 2. B · O(n)
  3. 3. D · f は g と同じ速さで増加し、上下から g の定数倍で抑えられる
  4. 4. A · Ω(n log n)
  5. 5. D · O(n)
  6. 6. D · 底の異なる対数は定数倍しか違わないから
  7. 7. B · いいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
  8. 8. C · V − 1 回のラウンドの後、まだ緩和できる辺があるかどうかを調べる

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