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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

メモ化（memoisation）とは何ですか？

  1. A再帰を自動的に等価なループに変換し、コールスタックを不要にすること
  2. B関数が戻った後にメモリを解放すること
  3. Cコードの各行の横にコメントを書くこと
  4. D関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
2.やさしい

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

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

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

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

クイックソートの最悪時間計算量は何ですか？

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

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

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

1、3、4 の硬貨で金額 6 をつくるとき、貪欲な「最大の硬貨から」方式は最適解と比べて何枚の硬貨を使いますか？

  1. A貪欲法は 3 枚、最適解は 3 枚
  2. B貪欲法は 3 枚、最適解は 2 枚
  3. C貪欲法は 2 枚、最適解は 2 枚
  4. D貪欲法は 4 枚、最適解は 3 枚
7.むずかしい

単方向連結リストでは、二分探索が O(log n) 時間にならないのはなぜですか？

  1. A連結リストはソートできないから
  2. Bインデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
  3. C二分探索には少なくとも 2 倍のメモリが必要だから
  4. D連結リストのノードでの比較は遅いから
8.むずかしい

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

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

解答

  1. 1. D · 関数呼び出しの結果を保存し、同じ呼び出しにはメモリから答えること
  2. 2. B · O(n)
  3. 3. A · 問題を解く、明確に定義された手順の有限の列
  4. 4. A · O(n²)
  5. 5. C · 各ステップで局所的に最良の選択をする
  6. 6. B · 貪欲法は 3 枚、最適解は 2 枚
  7. 7. B · インデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから
  8. 8. D · n 通りの結果をもつ決定木は、深さが少なくとも log₂ n でなければならないから

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