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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

分割統治アルゴリズムの 3 つのステップは何ですか？

  1. A分割、統治、結合
  2. B推測、確認、反復
  3. C読み込み、計算、書き出し
  4. Dソート、探索、返却
2.やさしい

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

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

マージソートの最悪時間計算量は何ですか？

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

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

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

動的計画法がマージソートを実質的に高速化しないのはなぜですか？

  1. A動的計画法はグラフ問題にしか使えず、配列には使えないから
  2. B部分問題が重複しないので、再利用するものがないから
  3. Cマージソートはすでに O(n) だから
  4. Dマージソートには再帰的な構造がないから
6.ふつう

n 要素の配列に対するマージソートの再帰は何段階になりますか？

  1. A約 √n
  2. B約 n / 2
  3. C約 log₂ n
  4. D約 n
7.むずかしい

ヘルド－カープの動的計画法アルゴリズムは巡回セールスマン問題を厳密に解きます。n 都市に対する実行時間は何ですか？

  1. AO(n² 2ⁿ)
  2. BO(n³)
  3. CO(n!)
  4. DO(2n²)
8.むずかしい

極大マッチングのすべての辺の両端点をとると頂点被覆が得られます。この被覆はどれくらいよいですか？

  1. A常に最小頂点被覆
  2. B最小値の高々 log n 倍
  3. C最適解と比べた品質は不明
  4. D最小頂点被覆のサイズの高々 2 倍

解答

  1. 1. A · 分割、統治、結合
  2. 2. B · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  3. 3. C · O(n log n)
  4. 4. A · O(n)
  5. 5. B · 部分問題が重複しないので、再利用するものがないから
  6. 6. C · 約 log₂ n
  7. 7. A · O(n² 2ⁿ)
  8. 8. D · 最小頂点被覆のサイズの高々 2 倍

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