Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah yang diterangkan oleh masa larian kes terburuk sesuatu algoritma?

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

Apakah log₂ 1024?

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

Masa larian sesuatu algoritma ialah O(n). Apakah pertumbuhan ini dipanggil?

1. ALinear
2. BLogaritma
3. CKuadratik
4. DMalar

Isihan pantas sentiasa menggunakan elemen pertama sebagai pangsi. Pada input manakah ia menunjukkan tingkah laku kes terburuk?

1. ATatasusunan dalam susunan rawak
2. BTatasusunan sepanjang 2
3. CTatasusunan yang sudah tersusun
4. DTatasusunan yang semua elemennya berbeza

Sesuatu fungsi menjalankan satu gelung n lelaran dan kemudian, secara berasingan, satu lagi gelung n lelaran. Apakah kerumitan masanya?

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

Carian pertama lebar pada graf tidak berpemberat mencari:

1. ALaluan terpendek dalam graf yang mengandungi pemberat sisi negatif
2. BPokok rentang minimum
3. CLaluan terpendek dari segi bilangan sisi dari nod permulaan
4. DSusunan topologi dalam semua graf

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

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

Dua perkara manakah yang mesti ditunjukkan untuk membuktikan bahawa masalah keputusan X ialah NP-lengkap?

1. AX boleh diturunkan kepada masalah dalam P, dan X dalam NP
2. BX dalam NP, dan masalah NP-lengkap yang diketahui boleh diturunkan kepada X dalam masa polinomial
3. CX tiada algoritma polinomial, dan X boleh diputuskan
4. DX dalam P, dan X boleh diturunkan kepada SAT