Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah log₂ 1024?

1. A512
2. B10
3. C12
4. D32

Apakah rekursi?

1. AFungsi yang memanggil dirinya sendiri pada input yang lebih kecil
2. BSejenis struktur data
3. CKaedah isihan
4. DGelung yang tidak pernah berakhir

Apakah tiga langkah algoritma bahagi dan takluk?

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

Batas bawah bagi isihan berasaskan perbandingan dalam kes terburuk ialah:

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

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

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

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

1. AMasalah itu boleh diselesaikan dalam masa malar
2. BSetiap submasalah mempunyai saiz yang sama
3. CPenyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya
4. DMasalah itu mempunyai tepat satu penyelesaian optimum, yang dikongsi oleh setiap submasalah

Mengapakah sebarang carian berasaskan perbandingan dalam tatasusunan tersusun memerlukan Ω(log n) perbandingan dalam kes terburuk?

1. APokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n
2. BCarian binari ialah satu-satunya algoritma yang mungkin, dan ia memerlukan log₂ n perbandingan
3. CSetiap elemen mesti dibandingkan sekurang-kurangnya sekali
4. DPerbandingan mengambil masa logaritma setiap satu

Bagaimanakah masalah jurujual kembara dikelaskan?

1. AIa dalam P kerana algoritma Dijkstra menyelesaikannya dengan melawat setiap bandar sekali
2. BIa tidak boleh diputuskan
3. CVersi keputusan ialah NP-lengkap dan versi pengoptimuman ialah NP-sukar
4. DVersi keputusan dalam P tetapi versi pengoptimuman NP-lengkap