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

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

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

アルゴリズムの最悪実行時間は何を表しますか？

1. Aサイズ n のランダムな入力に対する期待所要時間
2. B最小の入力に対する所要時間
3. C遅いコンピュータでの所要時間
4. Dサイズ n のすべての入力にわたる最大の所要時間

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

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

安定（stable）なソートアルゴリズムはどれですか？

1. Aクイックソート（一般的なインプレース版）
2. Bマージソート
3. Cヒープソート
4. D選択ソート（一般的な版）

問題が最適部分構造をもつとはどういう意味ですか？

1. A問題を定数時間で解ける
2. B最適解を部分問題の最適解から構成できる
3. Cすべての部分問題が同じサイズである
4. D問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから

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

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

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

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

ある NP 完全問題に対する多項式時間アルゴリズムを誰かが見つけたら、何が導かれますか？

1. ANP のすべての問題が多項式時間で解けることになり、P = NP となる
2. Bすべての指数時間アルゴリズムがただちに線形時間で動くようになる
3. C停止問題が決定可能になる
4. Dその 1 つの問題だけが P に移る