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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

次の実行時間のうち、多項式時間はどれですか？

  1. AO(2ⁿ)
  2. BO(n!)
  3. CO(n³)
  4. DO(nⁿ)
2.やさしい

隣接リストで格納されたグラフに対する深さ優先探索の時間計算量は何ですか？

  1. AO(V + E)
  2. BO(V × E)
  3. CO(V²)
  4. DO(E log V)
3.やさしい

順序が誤っている隣接要素を繰り返し交換するソートアルゴリズムはどれですか？

  1. Aバブルソート（Bubble sort）
  2. Bクイックソート（Quicksort）
  3. Cマージソート（Merge sort）
  4. Dヒープソート（Heap sort）
4.ふつう

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

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

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

  1. Aどの場合でも Bellman–Ford が必要
  2. BKruskal 法
  3. CDijkstra 法
  4. D深さ優先探索（DFS）
6.ふつう

ボトムアップの表を使って n 番目のフィボナッチ数を計算する時間計算量は何ですか？

  1. AO(2ⁿ)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
7.むずかしい

最後の 2 つの値だけを保持するループで n 番目のフィボナッチ数を計算する時間と領域のコストは何ですか？

  1. A時間 O(n)、領域 O(n)
  2. B時間 O(log n)、領域 O(n)
  3. C時間 O(2ⁿ)、領域 O(1)
  4. D時間 O(n)、領域 O(1)
8.むずかしい

一部の辺の重みが負のとき、ダイクストラ法が誤った結果を出すことがあるのはなぜですか？

  1. A無向グラフでしか動作しないから
  2. B負の数は優先度付きキューに格納できないから
  3. C頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから
  4. D負の辺があるたびに無限ループに陥るから

解答

  1. 1. C · O(n³)
  2. 2. A · O(V + E)
  3. 3. A · バブルソート（Bubble sort）
  4. 4. B · O(log n)
  5. 5. C · Dijkstra 法
  6. 6. C · O(n)
  7. 7. D · 時間 O(n)、領域 O(1)
  8. 8. C · 頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから

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