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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

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

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

再帰とは何ですか？

  1. Aソートの手法の一つ
  2. Bより小さな入力に対して自分自身を呼び出す関数
  3. C決して終わらないループ
  4. Dデータ構造の一種
4.ふつう

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

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

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

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

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

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

P と NP に関する記述として正しいものはどれですか？

  1. AP ≠ NP であることが証明されている
  2. BP に属するすべての問題は NP にも属する
  3. CNP の問題は高速に検証できない
  4. DNP は "not polynomial" を意味する
8.むずかしい

巡回セールスマン問題はどのように分類されますか？

  1. A決定版は NP 完全で、最適化版は NP 困難である
  2. B決定不能である
  3. Cダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
  4. D決定版は P に属するが、最適化版は NP 完全である

解答

  1. 1. A · 実行時間が入力サイズとともに増加しない
  2. 2. C · 未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
  3. 3. B · より小さな入力に対して自分自身を呼び出す関数
  4. 4. C · 各ステップで局所的に最良の選択をする
  5. 5. C · O(log n)
  6. 6. D · 開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
  7. 7. B · P に属するすべての問題は NP にも属する
  8. 8. A · 決定版は NP 完全で、最適化版は NP 困難である

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