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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

  1. A2 秒
  2. B4 秒
  3. C1 秒
  4. D8 秒
2.やさしい

それぞれ n 回実行される二重の入れ子ループを持つアルゴリズムの計算量は、通常どれですか？

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

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

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

問題が最適部分構造をもつとはどういう意味ですか？

  1. A問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから
  2. B問題を定数時間で解ける
  3. C最適解を部分問題の最適解から構成できる
  4. Dすべての部分問題が同じサイズである
5.ふつう

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

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

プリム法は最小全域木をどのように構築しますか？

  1. A閉路がなくなるまで最も高い辺を取り除く
  2. B開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
  3. Cすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える
  4. D幅優先探索を実行し、BFS 木を残す
7.むずかしい

最短単純路は多項式時間で見つけられます。一般のグラフで 2 頂点間の最長単純路を見つけることについて、何が知られていますか？

  1. ANP 困難である
  2. B常に O(V + E) で解ける
  3. C重みの符号を反転すればダイクストラ法で解ける
  4. D決定不能である
8.むずかしい

停止問題（halting problem）が示していることはどれですか？

  1. Aループは避けるべきである
  2. Bすべてのプログラムはいずれ停止する
  3. C一部のプログラムは高速なコンピュータでより速く動作するので、停止するかどうかはハードウェアに依存するから
  4. Dすべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない

解答

  1. 1. B · 4 秒
  2. 2. C · O(n²)
  3. 3. B · O(n)
  4. 4. C · 最適解を部分問題の最適解から構成できる
  5. 5. C · O(d(n + k))
  6. 6. B · 開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
  7. 7. A · NP 困難である
  8. 8. D · すべてのプログラムと入力について、それが停止するかどうかを判定できるアルゴリズムは存在しない

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