Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

1. AHeap sort
2. BMerge sort
3. CQuicksort
4. DBubble sort

Apa yang dimaksud base case pada fungsi rekursif?

1. APemanggilan yang memakai memori paling banyak
2. BBaris pertama fungsi
3. CKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
4. DKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. AHanya dapat dijalankan sekali
2. BSelalu memerlukan tepat satu detik
3. CMemproses tepat satu elemen per detik waktu eksekusi
4. DWaktu eksekusinya tidak bertambah seiring ukuran input

Algoritma pengurutan manakah yang stabil (stable)?

1. AMerge sort
2. BSelection sort (versi yang umum)
3. CHeap sort
4. DQuicksort (versi in-place yang umum)

Bagaimana algoritma Prim membangun minimum spanning tree?

1. AMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
2. BMenjalankan breadth-first search dan menyimpan pohon BFS
3. CMenghapus sisi termahal sampai tidak ada siklus tersisa
4. DMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 100
2. BSekitar 20
3. CSekitar 500,000
4. DSekitar 1,000

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ABerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
2. BDapat diselesaikan dalam waktu polinomial
3. CTermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
4. DTidak mungkin diselesaikan

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n³)
4. DΘ(n² log n)