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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

二分探索は入力に何を要求しますか？

  1. A配列の要素が 1000 個以下であること
  2. B配列の長さが 2 のべき乗であること
  3. C配列がソートされていること
  4. D配列が正の数だけを含むこと
2.やさしい

アルゴリズムとは何ですか？

  1. Aグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
  2. B数値を格納するデータ構造
  3. C数式を書くために設計されたプログラミング言語
  4. D問題を解く、明確に定義された手順の有限の列
3.やさしい

あるループは i = 1 から始まり、i > n となるまで各反復で i を 2 倍にします。何回反復しますか？

  1. A約 n / 2 回
  2. B約 log₂ n 回
  3. C約 n 回
  4. D約 n² 回
4.ふつう

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

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

単純な再帰の階乗関数 fact(n) = n × fact(n − 1) はどれだけのスタック領域を使いますか？

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

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

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

マスター定理を用いると、T(n) = 8T(n/2) + O(n²) の解はどれですか？

  1. AΘ(n² log n)
  2. BΘ(n log n)
  3. CΘ(n³)
  4. DΘ(n²)
8.むずかしい

問題が NP 完全（NP-complete）であるのは、次のどの場合ですか？

  1. A停止問題のように、NP に属さないがすべての NP 問題より難しい
  2. B多項式時間で解ける
  3. CNP に属し、すべての NP 問題が多項式時間でその問題に帰着できる
  4. D解くことが不可能である

解答

  1. 1. C · 配列がソートされていること
  2. 2. D · 問題を解く、明確に定義された手順の有限の列
  3. 3. B · 約 log₂ n 回
  4. 4. B · O(1)
  5. 5. B · O(n)
  6. 6. A · O(log n)
  7. 7. C · Θ(n³)
  8. 8. C · NP に属し、すべての NP 問題が多項式時間でその問題に帰着できる

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