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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

順序が誤っている隣接要素を繰り返し交換するソートアルゴリズムはどれですか？

  1. Aヒープソート（Heap sort）
  2. Bバブルソート（Bubble sort）
  3. Cクイックソート（Quicksort）
  4. Dマージソート（Merge sort）
2.やさしい

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

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

配列の要素にインデックスでアクセスするのにかかる時間は次のどれですか？

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

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

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

O(n²) のアルゴリズムは O(n³) でもあると言うのは正しいですか？

  1. Aはい。Big O は上界であり、n² は n³ より速く増加しないから
  2. Bいいえ。n が大きいとき n³ は n² より小さいから
  3. Cいいえ。Big O は常に関数の正確な増加率を述べなければならないから
  4. Dはい。ただし n が 100 より小さい場合に限る
6.ふつう

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

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

漸化式 T(n) = 2T(n/2) + n log n の解は何ですか？

  1. AΘ(n²)
  2. BΘ(n log² n)
  3. CΘ(n log n)
  4. DΘ(n)
8.むずかしい

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

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

解答

  1. 1. B · バブルソート（Bubble sort）
  2. 2. C · 配列がソートされていること
  3. 3. C · O(1)
  4. 4. B · 各ステップで局所的に最良の選択をする
  5. 5. A · はい。Big O は上界であり、n² は n³ より速く増加しないから
  6. 6. A · 始点ノードからの辺の数で測った最短経路
  7. 7. B · Θ(n log² n)
  8. 8. D · クイックセレクトは期待 O(n) で動作し、中央値の中央値法は最悪 O(n) を保証する

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