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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

順序が誤っている隣接要素を繰り返し交換するソートアルゴリズムはどれですか？

  1. Aヒープソート（Heap sort）
  2. Bクイックソート（Quicksort）
  3. Cバブルソート（Bubble sort）
  4. Dマージソート（Merge sort）
2.やさしい

3n² + 5n + 2 の Big O は何ですか？

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

log₂ 1024 はいくつですか？

  1. A512
  2. B12
  3. C32
  4. D10
4.ふつう

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

  1. A可能なすべての解を試す
  2. B常に最適解を与える
  3. C再帰のみを使用する
  4. D各ステップで局所的に最良の選択をする
5.ふつう

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

  1. A貪欲法は 4 枚、最適解は 3 枚
  2. B貪欲法は 2 枚、最適解は 2 枚
  3. C貪欲法は 3 枚、最適解は 2 枚
  4. D貪欲法は 3 枚、最適解は 3 枚
6.ふつう

多くのライブラリのソート関数が、非常に小さな部分配列では挿入ソートに切り替えるのはなぜですか？

  1. A大きな入力では、挿入ソートは他のどのソートアルゴリズムよりメモリが少なくて済むから
  2. B再帰アルゴリズムは 10 要素未満の配列を扱えないから
  3. C挿入ソートは最悪の場合 O(n log n) だから
  4. D挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
7.むずかしい

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

  1. A多項式でない問題
  2. B多項式時間で解けない問題
  3. C証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
  4. Dどのアルゴリズムでも解けない問題
8.むずかしい

little-o 記法について正しい記述はどれですか？

  1. A2n はゆっくり増加するので、2n = o(n)
  2. Bn² = o(n)
  3. Cどの関数も自分自身の little-o なので、n = o(n)
  4. Dn = o(n²) だが、n は o(n) ではない

解答

  1. 1. C · バブルソート（Bubble sort）
  2. 2. A · O(n²)
  3. 3. D · 10
  4. 4. D · 各ステップで局所的に最良の選択をする
  5. 5. C · 貪欲法は 3 枚、最適解は 2 枚
  6. 6. D · 挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
  7. 7. C · 証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
  8. 8. D · n = o(n²) だが、n は o(n) ではない

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