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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

選択ソート（selection sort）はどのように動作しますか？

  1. A順序が逆になっている隣り合う要素を繰り返し交換する
  2. Bシフトによって各要素を成長していくソート済み部分に挿入する
  3. C未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
  4. D配列を半分に分け、それらをマージする
2.やさしい

3n² + 5n + 2 の Big O は何ですか？

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

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

  1. A線形
  2. B定数
  3. C対数的
  4. D2 乗
4.ふつう

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

  1. A底の異なる対数は定数倍しか違わないから
  2. B対数は常に整数に丸められるから
  3. C計算機科学のすべての対数は底が 10 なので、省略されているから
  4. D底は n が小さいときにしか問題にならないから
5.ふつう

ワーシャル－フロイド法は何を、どれくらいの速さで計算しますか？

  1. Aトポロジカル順序を O(V²) で
  2. Bすべての頂点対の間の最短経路を O(V³) で
  3. C1 つの始点から他のすべての頂点への最短経路を O(V + E) で
  4. D最小全域木を O(E log V) で
6.ふつう

安定（stable）なソートアルゴリズムはどれですか？

  1. A選択ソート（一般的な版）
  2. Bヒープソート
  3. Cクイックソート（一般的なインプレース版）
  4. Dマージソート
7.むずかしい

シュトラッセンのアルゴリズムは、半分のサイズのブロックの再帰的な掛け算を 8 回ではなく 7 回にして行列を掛けます。実行時間は何ですか？

  1. AΘ(n2)
  2. BΘ(n² log n)
  3. CΘ(nlog₂ 7)、約 n2.81
  4. DΘ(n³)
8.むずかしい

極大マッチングのすべての辺の両端点をとると頂点被覆が得られます。この被覆はどれくらいよいですか？

  1. A最小頂点被覆のサイズの高々 2 倍
  2. B最小値の高々 log n 倍
  3. C最適解と比べた品質は不明
  4. D常に最小頂点被覆

解答

  1. 1. C · 未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
  2. 2. C · O(n²)
  3. 3. A · 線形
  4. 4. A · 底の異なる対数は定数倍しか違わないから
  5. 5. B · すべての頂点対の間の最短経路を O(V³) で
  6. 6. D · マージソート
  7. 7. C · Θ(nlog₂ 7)、約 n2.81
  8. 8. A · 最小頂点被覆のサイズの高々 2 倍

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