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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

再帰とは何ですか？

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

平均実行時間は何を表しますか？

  1. A最良の場合と最悪の場合の実行時間の中間の値
  2. Bサイズ n の入力の与えられた分布に対する期待所要時間
  3. C最も一般的なコンピュータでの所要時間
  4. D平均的な長さの入力に対する所要時間
3.やさしい

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

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

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

  1. A対数時間
  2. B定数時間
  3. C指数時間
  4. D線形時間
5.ふつう

あるクイックソートは常に最初の要素をピボットに使います。どの入力で最悪の振る舞いを示しますか？

  1. A長さ 2 の配列
  2. Bランダムな順序の配列
  3. Cすでにソートされている配列
  4. Dすべての要素が異なる配列
6.ふつう

重みなしグラフでの幅優先探索（BFS）で求められるものはどれですか？

  1. A負の辺の重みを含むグラフでの最短経路
  2. Bすべてのグラフにおけるトポロジカル順序
  3. C始点ノードからの辺の数で測った最短経路
  4. D最小全域木
7.むずかしい

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

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

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

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

解答

  1. 1. B · より小さな入力に対して自分自身を呼び出す関数
  2. 2. B · サイズ n の入力の与えられた分布に対する期待所要時間
  3. 3. C · O(n)
  4. 4. C · 指数時間
  5. 5. C · すでにソートされている配列
  6. 6. C · 始点ノードからの辺の数で測った最短経路
  7. 7. D · NP に属し、すべての NP 問題が多項式時間でその問題に帰着できる
  8. 8. A · 最小頂点被覆のサイズの高々 2 倍

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