Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kes asas bagi fungsi rekursif?

1. AKes yang dijawab terus tanpa membuat panggilan rekursif lain
2. BPanggilan yang menggunakan paling banyak memori
3. CKes dengan input terbesar, yang dikendalikan sebelum sebarang panggilan rekursif
4. DBaris pertama fungsi

Satu gelung bermula dengan i = 1 dan menggandakan i pada setiap lelaran sehingga i > n. Berapa banyak lelaran yang dijalankannya?

1. AKira-kira n²
2. BKira-kira n / 2
3. CKira-kira n
4. DKira-kira log₂ n

Algoritma dengan dua gelung bersarang, masing-masing berjalan n kali, biasanya mempunyai kerumitan yang mana?

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

Berapa banyak ruang tindanan yang digunakan oleh fungsi faktorial rekursif mudah fact(n) = n × fact(n − 1)?

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

Apakah kerumitan masa bagi: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

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

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

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

Mengambil kedua-dua hujung setiap sisi dalam padanan maksimal memberikan litupan bucu. Sebaik manakah litupan ini?

1. APaling banyak log n kali minimum
2. BPaling banyak dua kali ganda saiz litupan bucu minimum
3. CMutunya tidak diketahui berbanding optimum
4. DSentiasa litupan bucu minimum