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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

n 個の要素を持つ未ソートの配列に対する線形探索（linear search）の時間計算量（最悪の場合）は何ですか？

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

再帰とは何ですか？

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

二分探索は入力に何を要求しますか？

  1. A配列の長さが 2 のべき乗であること
  2. B配列がソートされていること
  3. C配列が正の数だけを含むこと
  4. D配列の要素が 1000 個以下であること
4.ふつう

満杯になると容量を2倍にする動的配列に要素を追加する操作の償却（amortised）時間計算量は何ですか？

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

ならし解析（amortised analysis）は何を測りますか？

  1. A最良の入力に対するアルゴリズムのコスト
  2. B最悪の操作列にわたる操作 1 回あたりの平均コスト
  3. Cランダムな入力に対する期待コスト
  4. D操作列のどこかにある、最もコストの高い 1 回の操作のコスト
6.ふつう

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

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

ベルマン－フォード法は、始点から到達可能な負の重みの閉路をどのように検出しますか？

  1. Aダイクストラ法を 2 回実行し、2 つの距離の結果を比べる
  2. BV − 1 回のラウンドの後、まだ緩和できる辺があるかどうかを調べる
  3. C負の重みをもつ辺があるかどうかを調べる
  4. D深さ優先探索で閉路を数える
8.むずかしい

ソート済み配列における比較に基づく探索が、最悪の場合 Ω(log n) 回の比較を必要とするのはなぜですか？

  1. A比較 1 回ごとに対数時間がかかるから
  2. Bすべての要素を少なくとも一度比較しなければならないから
  3. Cn 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから
  4. D二分探索が唯一可能なアルゴリズムであり、log₂ n 回の比較が必要だから

解答

  1. 1. C · O(n)
  2. 2. D · より小さな入力に対して自分自身を呼び出す関数
  3. 3. B · 配列がソートされていること
  4. 4. B · O(1)
  5. 5. B · 最悪の操作列にわたる操作 1 回あたりの平均コスト
  6. 6. C · O(n)
  7. 7. B · V − 1 回のラウンドの後、まだ緩和できる辺があるかどうかを調べる
  8. 8. C · n 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから

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