Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah tiga langkah algoritma bahagi dan takluk?

1. ABaca, kira, tulis
2. BTeka, semak, ulang
3. CBahagi, takluk, gabung
4. DIsih, cari, kembali

Algoritma O(n²) mengambil 1 saat untuk n = 1000. Kira-kira berapa lamakah ia mengambil masa untuk n = 2000?

1. A8 saat
2. B4 saat
3. C2 saat
4. D1 saat

Apakah maksud f(n) = Θ(g(n))?

1. Af tumbuh pada kadar yang sama dengan g, dibatasi atas dan bawah oleh gandaan malar g
2. Bf sentiasa lebih kecil daripada g bagi setiap n, jadi g membatasinya dari atas tetapi tidak pernah dari bawah
3. Cf tumbuh lebih pantas daripada g secara ketat
4. Df tumbuh lebih perlahan daripada g secara ketat

Algoritma tamak (greedy):

1. AMembuat pilihan terbaik setempat pada setiap langkah
2. BMencuba setiap penyelesaian yang mungkin
3. CHanya menggunakan rekursi
4. DSentiasa memberikan penyelesaian optimum

Dalam masalah pemilihan aktiviti, peraturan tamak manakah yang sentiasa memberikan bilangan maksimum aktiviti yang tidak bertindih?

1. APilih aktiviti dengan pertindihan paling sedikit dahulu, kemudian ulang dengan yang serasi
2. BPilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
3. CPilih aktiviti yang bermula paling awal
4. DPilih aktiviti terpendek dahulu

Hubungan jadi semula T(n) = 2T(n/2) + O(n) mempunyai penyelesaian:

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

Apakah yang dibuktikan oleh teorem Cook–Levin?

1. AMasalah kebolehpuasan Boolean (SAT) ialah NP-lengkap
2. BSetiap masalah NP boleh diselesaikan dalam masa eksponen
3. CP tidak sama dengan NP
4. DMasalah penghentian tidak boleh diputuskan

Takrifan kelas NP yang manakah betul?

1. AMasalah yang tiada algoritma boleh menyelesaikannya
2. BMasalah keputusan yang jawapan ya-nya boleh disahkan dalam masa polinomial dengan adanya sijil
3. CMasalah yang bukan polinomial
4. DMasalah yang tidak boleh diselesaikan dalam masa polinomial