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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

すでにソート済みの配列に対する挿入ソートの最良時間計算量は何ですか？

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

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

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

アルゴリズムとは何ですか？

  1. A数式を書くために設計されたプログラミング言語
  2. B数値を格納するデータ構造
  3. Cグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
  4. D問題を解く、明確に定義された手順の有限の列
4.ふつう

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

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

n 要素の配列に対するマージソートの再帰は何段階になりますか？

  1. A約 log₂ n
  2. B約 √n
  3. C約 n / 2
  4. D約 n
6.ふつう

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

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

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

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

問題が NP 完全（NP-complete）であるのは、次のどの場合ですか？

  1. A停止問題のように、NP に属さないがすべての NP 問題より難しい
  2. B多項式時間で解ける
  3. CNP に属し、すべての NP 問題が多項式時間でその問題に帰着できる
  4. D解くことが不可能である

解答

  1. 1. C · O(n)
  2. 2. A · 線形
  3. 3. D · 問題を解く、明確に定義された手順の有限の列
  4. 4. B · O(n)
  5. 5. A · 約 log₂ n
  6. 6. C · O(2ⁿ)
  7. 7. D · 最小頂点被覆のサイズの高々 2 倍
  8. 8. C · NP に属し、すべての NP 問題が多項式時間でその問題に帰着できる

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