Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan mana yang memilih pivot dan mempartisi array menjadi elemen yang lebih kecil dan lebih besar?

1. AInsertion sort
2. BBubble sort
3. CQuicksort
4. DMerge sort

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada input terkecil
2. BWaktu yang diharapkan pada input acak berukuran n
3. CWaktu yang diperlukan pada komputer yang lambat
4. DWaktu maksimum yang diperlukan atas semua input berukuran n

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Bagaimana algoritma Prim membangun minimum spanning tree?

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

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Apa artinya suatu masalah memiliki optimal substructure?

1. AMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
2. BSetiap submasalah memiliki ukuran yang sama
3. CMasalah itu dapat diselesaikan dalam waktu konstan
4. DSolusi optimal dapat dibangun dari solusi optimal submasalahnya

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

1. AMenggunakan rekursi hanya pada sisi kiri
2. BMemilih pivot secara acak seragam
3. CSelalu memilih elemen pertama
4. DMengurutkan input sebelum menjalankan quicksort

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. APohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
2. BSetiap elemen harus dibandingkan setidaknya sekali
3. CBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
4. DSetiap perbandingan memerlukan waktu logaritmik