Lembar kerja Algoritma & kompleksitas dengan jawaban

Bagaimana cara kerja selection sort?

1. AMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
2. BBerulang kali menukar elemen bersebelahan yang urutannya salah
3. CBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
4. DMembagi array menjadi dua bagian lalu menggabungkannya

Berapa nilai log₂ 1024?

1. A32
2. B12
3. C10
4. D512

Suatu masalah biasanya disebut tractable jika:

1. AHanya dapat diselesaikan dengan mencoba setiap kemungkinan
2. BDapat diselesaikan dalam waktu konstan
3. CTidak memiliki solusi
4. DDapat diselesaikan dalam waktu polinomial

Rekurens T(n) = 2T(n/2) + O(1) menghasilkan apa?

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

Rekurens T(n) = T(n − 1) + O(n) menghasilkan apa?

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

Apa yang diukur oleh analisis amortisasi?

1. ABiaya rata-rata per operasi atas urutan operasi kasus terburuk
2. BBiaya yang diharapkan atas input acak
3. CBiaya satu operasi yang paling mahal di mana pun dalam urutan itu
4. DBiaya algoritma pada input terbaik

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. AHalting problem menjadi decidable
2. BSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
3. CHanya masalah itu yang pindah ke P
4. DSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear