Lembaran kerja Algoritma & kerumitan dengan jawapan

Berapa banyak memori tambahan yang digunakan oleh isihan cantum berasaskan tatasusunan piawai?

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

Apakah maksudnya jika sesuatu operasi berjalan dalam masa O(1)?

1. AIa hanya boleh dijalankan sekali
2. BIa memproses tepat satu elemen bagi setiap saat masa larian
3. CIa sentiasa mengambil tepat satu saat
4. DMasa larinya tidak bertambah dengan saiz input

Apakah tiga langkah algoritma bahagi dan takluk?

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

Bagaimanakah algoritma Prim membina pokok rentang minimum?

1. AIa menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
2. BIa mengisih semua sisi mengikut pemberat dan menambah setiap satu kecuali jika ia membentuk kitaran dalam hutan
3. CIa menjalankan carian pertama lebar dan mengekalkan pokok BFS
4. DIa membuang sisi paling mahal sehingga tiada kitaran tinggal

Apakah yang diukur oleh analisis teramortisasi?

1. AKos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
2. BKos dijangka merentasi input rawak
3. CKos algoritma pada input terbaik
4. DKos satu operasi yang paling mahal di mana-mana dalam jujukan itu

Carian pertama lebar pada graf tidak berpemberat mencari:

1. APokok rentang minimum
2. BLaluan terpendek dari segi bilangan sisi dari nod permulaan
3. CSusunan topologi dalam semua graf
4. DLaluan terpendek dalam graf yang mengandungi pemberat sisi negatif

Laluan ringkas terpendek boleh dicari dalam masa polinomial. Apakah yang diketahui tentang mencari laluan ringkas terpanjang antara dua bucu dalam graf am?

1. AIa tidak boleh diputuskan
2. BIa sentiasa boleh diselesaikan dalam O(V + E)
3. CIa boleh diselesaikan oleh algoritma Dijkstra dengan pemberat dinegatifkan
4. DIa NP-sukar

Bagaimanakah n! dan 2ⁿ dibandingkan untuk n yang besar?

1. AKeduanya tumbuh pada kadar yang sama
2. B2ⁿ tumbuh lebih pantas daripada n!
3. Cn! ialah O(n²)
4. Dn! tumbuh lebih pantas daripada 2ⁿ