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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

再帰とは何ですか？

  1. Aデータ構造の一種
  2. Bより小さな入力に対して自分自身を呼び出す関数
  3. C決して終わらないループ
  4. Dソートの手法の一つ
3.やさしい

ある O(n²) アルゴリズムは n = 1000 で 1 秒かかります。n = 2000 ではおよそ何秒かかりますか？

  1. A1 秒
  2. B4 秒
  3. C8 秒
  4. D2 秒
4.ふつう

k 進数で d 桁の n 個の整数に対する LSD 基数ソートの実行時間は何ですか？

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

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

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

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

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

トポロジカルソートが可能なのは、次のどのグラフだけですか？

  1. A有向非巡回グラフ（DAG）
  2. B負の重みを持つグラフ
  3. C完全グラフ
  4. D無向グラフ
8.むずかしい

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

  1. AΘ(n)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n log² n)

解答

  1. 1. A · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  2. 2. B · より小さな入力に対して自分自身を呼び出す関数
  3. 3. B · 4 秒
  4. 4. A · O(d(n + k))
  5. 5. D · O(n)
  6. 6. B · O(mn)
  7. 7. A · 有向非巡回グラフ（DAG）
  8. 8. D · Θ(n log² n)

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