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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

0 から k の範囲の n 個の整数に対する計数ソート（counting sort）の実行時間は何ですか？

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

次の実行時間のうち、多項式時間はどれですか？

  1. AO(nⁿ)
  2. BO(n!)
  3. CO(2ⁿ)
  4. DO(n³)
4.ふつう

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

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

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

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

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

  1. ADijkstra 法
  2. BKruskal 法
  3. Cどの場合でも Bellman–Ford が必要
  4. D深さ優先探索（DFS）
7.むずかしい

未ソートの配列から k 番目に小さい要素を選択することについて、正しい記述はどれですか？

  1. Aクイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する
  2. Bクイックセレクトはピボットの片側だけで再帰するので、最悪でも O(log n) で動作する
  3. C選択は O(n²) でしか行えない
  4. D選択にはソートが必要なので、常に Ω(n log n) が必要である
8.むずかしい

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

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

解答

  1. 1. D · O(n)
  2. 2. D · O(n + k)
  3. 3. D · O(n³)
  4. 4. D · O(2ⁿ)
  5. 5. D · すでにソートされている配列
  6. 6. A · Dijkstra 法
  7. 7. A · クイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する
  8. 8. D · インデックスによる直接アクセスがないので、中央の要素に到達するのに O(n) ステップかかるから

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