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

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

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

選択ソート（selection sort）はどのように動作しますか？

1. A順序が逆になっている隣り合う要素を繰り返し交換する
2. B配列を半分に分け、それらをマージする
3. C未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
4. Dシフトによって各要素を成長していくソート済み部分に挿入する

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

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

動的計画法がマージソートを実質的に高速化しないのはなぜですか？

1. A部分問題が重複しないので、再利用するものがないから
2. B動的計画法はグラフ問題にしか使えず、配列には使えないから
3. Cマージソートはすでに O(n) だから
4. Dマージソートには再帰的な構造がないから

プリム法は最小全域木をどのように構築しますか？

1. Aすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える
2. B幅優先探索を実行し、BFS 木を残す
3. C閉路がなくなるまで最も高い辺を取り除く
4. D開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える

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

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

little-o 記法について正しい記述はどれですか？

1. A2n はゆっくり増加するので、2n = o(n)
2. Bn = o(n²) だが、n は o(n) ではない
3. Cどの関数も自分自身の little-o なので、n = o(n)
4. Dn² = o(n)

log(n!) について正しい評価はどれですか？

1. AΘ(n)
2. BΘ(log n)
3. CΘ(n log n)
4. DΘ(n²)