Lembaran kerja Algoritma & kerumitan dengan jawapan

Algoritma isihan manakah yang memilih pangsi dan memetakan tatasusunan kepada elemen yang lebih kecil dan lebih besar?

1. AIsihan gelembung
2. BIsihan sisipan
3. CIsihan cantum
4. DIsihan pantas

Apakah yang diterangkan oleh masa larian kes terburuk sesuatu algoritma?

1. AMasa maksimum yang diambil merentasi semua input bersaiz n
2. BMasa dijangka yang diambil pada input rawak bersaiz n
3. CMasa yang diambil pada komputer yang perlahan
4. DMasa yang diambil pada input terkecil

Apakah algoritma?

1. ABahasa pengaturcaraan yang direka untuk menulis formula matematik
2. BJujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
3. CStruktur data yang menyimpan nombor
4. DMana-mana program komputer yang mempunyai antara muka grafik

Mengapakah banyak rutin isihan pustaka bertukar kepada isihan sisipan untuk subtatasusunan yang sangat kecil?

1. AAlgoritma rekursif tidak boleh mengendalikan tatasusunan di bawah 10 elemen
2. BIsihan sisipan mempunyai overhed yang rendah dan pantas pada input kecil atau hampir tersusun
3. CIsihan sisipan menggunakan memori lebih sedikit daripada mana-mana algoritma pengisihan lain pada input besar
4. DIsihan sisipan ialah O(n log n) dalam kes terburuk

Apakah kerumitan masa teramortisasi bagi menambah pada tatasusunan dinamik yang menggandakan kapasitinya apabila penuh?

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

Kira-kira berapa banyak perbandingan yang diperlukan oleh carian binari dalam kes terburuk pada tatasusunan tersusun 1,000,000 elemen?

1. AKira-kira 20
2. BKira-kira 500,000
3. CKira-kira 100
4. DKira-kira 1,000

Teknik manakah yang memberikan masa larian dijangka O(n log n) bagi isihan pantas pada sebarang input?

1. AMemilih pangsi secara seragam rawak
2. BSentiasa memilih elemen pertama
3. CMenggunakan rekursi pada sebelah kiri sahaja
4. DMengisih input sebelum menjalankan isihan pantas

Apakah yang akan menyusul jika seseorang menemui algoritma masa polinomial untuk satu masalah NP-lengkap?

1. ASetiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
2. BHanya satu masalah itu berpindah ke dalam P
3. CSemua algoritma masa eksponen serta-merta berjalan dalam masa linear
4. DMasalah penghentian menjadi boleh diputuskan