1.Mudah
Apa yang dimaksud base case pada fungsi rekursif?
- ABaris pertama fungsi
- BKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
- CPemanggilan yang memakai memori paling banyak
- DKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
2.Mudah
Suatu masalah biasanya disebut tractable jika:
- AHanya dapat diselesaikan dengan mencoba setiap kemungkinan
- BDapat diselesaikan dalam waktu polinomial
- CTidak memiliki solusi
- DDapat diselesaikan dalam waktu konstan
3.Mudah
Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?
- AΩ (Big Omega)
- BΘ (Big Theta)
- CO (Big O)
- Do (little o)
4.Sedang
Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?
- ASekitar 100
- BSekitar 1,000
- CSekitar 20
- DSekitar 500,000
5.Sedang
Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?
- AMinimum spanning tree dalam O(E log V)
- BLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)
- CUrutan topologis dalam O(V²)
- DLintasan terpendek antara semua pasangan simpul dalam O(V³)
6.Sedang
Algoritma pengurutan manakah yang stabil (stable)?
- AQuicksort (versi in-place yang umum)
- BSelection sort (versi yang umum)
- CMerge sort
- DHeap sort
7.Sulit
Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?
- AMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
- BMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
- CMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
- DMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
8.Sulit
Suatu masalah disebut NP-complete jika masalah tersebut:
- ABerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
- BTidak mungkin diselesaikan
- CTermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
- DDapat diselesaikan dalam waktu polinomial
Kunci jawaban
- 1. D · Kasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
- 2. B · Dapat diselesaikan dalam waktu polinomial
- 3. A · Ω (Big Omega)
- 4. C · Sekitar 20
- 5. D · Lintasan terpendek antara semua pasangan simpul dalam O(V³)
- 6. C · Merge sort
- 7. B · Mereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
- 8. C · Termasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
Penyelesaian lengkap langkah demi langkah: latih topik ini di examproblems.com.