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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

分割統治アルゴリズムの 3 つのステップは何ですか？

  1. A分割、統治、結合
  2. B推測、確認、反復
  3. C読み込み、計算、書き出し
  4. Dソート、探索、返却
2.やさしい

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

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

ある操作が O(1) 時間で動作するとはどういう意味ですか？

  1. A実行時間 1 秒あたりちょうど 1 要素を処理する
  2. B一度しか実行できない
  3. C実行時間が入力サイズとともに増加しない
  4. D常にちょうど 1 秒かかる
4.ふつう

貪欲法（greedy algorithm）の説明として正しいものはどれですか？

  1. A各ステップで局所的に最良の選択をする
  2. B常に最適解を与える
  3. C可能なすべての解を試す
  4. D再帰のみを使用する
5.ふつう

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

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

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

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

新しい問題 X が NP 困難であることを示すには、何をしなければなりませんか？

  1. A既知の NP 困難な問題を多項式時間で X に帰着させる
  2. BX を多項式時間で既知の NP 困難な問題に帰着させる
  3. CX には小さな入力に対する多項式アルゴリズムがないことを示す
  4. DX を多項式時間で検証できることを示す
8.むずかしい

トポロジカルソートが可能なのは、次のどのグラフだけですか？

  1. A有向非巡回グラフ（DAG）
  2. B無向グラフ
  3. C負の重みを持つグラフ
  4. D完全グラフ

解答

  1. 1. A · 分割、統治、結合
  2. 2. C · バブルソート（Bubble sort）
  3. 3. C · 実行時間が入力サイズとともに増加しない
  4. 4. A · 各ステップで局所的に最良の選択をする
  5. 5. A · O(mn)
  6. 6. C · マージソート
  7. 7. A · 既知の NP 困難な問題を多項式時間で X に帰着させる
  8. 8. A · 有向非巡回グラフ（DAG）

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