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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

アルゴリズムの最悪実行時間は何を表しますか？

  1. A最小の入力に対する所要時間
  2. Bサイズ n のすべての入力にわたる最大の所要時間
  3. C遅いコンピュータでの所要時間
  4. Dサイズ n のランダムな入力に対する期待所要時間
2.やさしい

あるアルゴリズムの実行時間は O(n) です。この増加は何と呼ばれますか？

  1. A線形
  2. B2 乗
  3. C定数
  4. D対数的
3.やさしい

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

  1. A6 秒
  2. B3 秒
  3. C9 秒
  4. D12 秒
4.ふつう

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

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

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

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

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

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

閉路を作らない最も安い辺を繰り返し追加して最小全域木を求めるアルゴリズムはどれですか？

  1. A一つのノードから始める Prim 法
  2. BDijkstra 法
  3. CFloyd–Warshall
  4. DKruskal 法
8.むずかしい

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

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

解答

  1. 1. B · サイズ n のすべての入力にわたる最大の所要時間
  2. 2. A · 線形
  3. 3. A · 6 秒
  4. 4. B · 最適解を部分問題の最適解から構成できる
  5. 5. B · O(n)
  6. 6. A · 部分問題が重複しないので、再利用するものがないから
  7. 7. D · Kruskal 法
  8. 8. D · NP 困難である

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