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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

再帰とは何ですか？

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

ある O(n) アルゴリズムは n = 100 万で 3 秒かかります。n = 200 万ではおよそ何秒かかりますか？

  1. A6 秒
  2. B12 秒
  3. C3 秒
  4. D9 秒
3.やさしい

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

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

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

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

V 個の頂点と E 本の辺をもつグラフに対するベルマン－フォード法の時間計算量は何ですか？

  1. AO(V³ × E)
  2. BO(V × E)
  3. CO(E log V)
  4. DO(V + E)
6.ふつう

動的計画法（dynamic programming）が有効なのは、問題が次の性質を持つときです。

  1. Aループが一つだけ
  2. Bランダムな入力のみ
  3. C重複する部分問題と最適部分構造
  4. D部分問題がまったくないので、1 ステップで解ける
7.むずかしい

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

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

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

  1. A常に先頭の要素を選ぶ
  2. Bクイックソートを実行する前に入力をソートする
  3. C左側にのみ再帰を使う
  4. Dピボットを一様ランダムに選ぶ

解答

  1. 1. B · より小さな入力に対して自分自身を呼び出す関数
  2. 2. A · 6 秒
  3. 3. D · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  4. 4. C · O(2ⁿ)
  5. 5. B · O(V × E)
  6. 6. C · 重複する部分問題と最適部分構造
  7. 7. C · いいえ。下界はすべての入力にわたる最悪の場合に適用されるのであって、すべての入力に適用されるわけではない
  8. 8. D · ピボットを一様ランダムに選ぶ

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