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. CBaris pertama fungsi
4. DKes dengan input terbesar, yang dikendalikan sebelum sebarang panggilan rekursif

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 kerumitan masa kes terburuk isihan cantum?

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

Apakah penyelesaian hubungan jadi semula T(n) = T(n/2) + O(1)?

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

Mengapakah asas logaritma biasanya ditinggalkan dalam Big O, seperti dalam O(log n)?

1. ALogaritma sentiasa dibundarkan kepada integer
2. BSemua logaritma dalam sains komputer berasas 10, jadi ia tersirat
3. CLogaritma dengan asas berbeza hanya berbeza oleh faktor malar
4. DAsas hanya penting untuk n yang kecil

Apakah yang dikira oleh algoritma Floyd–Warshall, dan sepantas mana?

1. ALaluan terpendek dari satu bucu sumber ke semua bucu lain dalam O(V + E)
2. BPokok rentang minimum dalam O(E log V)
3. CSusunan topologi dalam O(V²)
4. DLaluan terpendek antara semua pasangan bucu dalam O(V³)

Algoritma pengaturcaraan dinamik Held–Karp menyelesaikan masalah jurujual kembara dengan tepat. Apakah masa larinya untuk n bandar?

1. AO(2^n²)
2. BO(n!)
3. CO(n³)
4. DO(n² 2ⁿ)

Apakah yang dibuktikan oleh teorem Cook–Levin?

1. AMasalah penghentian tidak boleh diputuskan
2. BP tidak sama dengan NP
3. CMasalah kebolehpuasan Boolean (SAT) ialah NP-lengkap
4. DSetiap masalah NP boleh diselesaikan dalam masa eksponen