Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

1. AArray tidak boleh berisi lebih dari 1000 elemen
2. BPanjang array harus pangkat dua
3. CArray hanya boleh berisi bilangan positif
4. DArray harus terurut

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

1. AQuicksort
2. BMerge sort
3. CHeap sort
4. DBubble sort

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

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

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar √n
2. BSekitar n / 2
3. CSekitar n
4. DSekitar log₂ n

Berapa kompleksitas waktu kasus terburuk quicksort?

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

Apa artinya suatu masalah memiliki optimal substructure?

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

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

1. ASelalu merupakan minimum vertex cover
2. BPaling banyak dua kali ukuran minimum vertex cover
3. CKualitasnya tidak diketahui dibandingkan optimum
4. DPaling banyak log n kali minimum

Definisi kelas NP manakah yang benar?

1. AMasalah yang tidak polinomial
2. BMasalah keputusan yang jawaban "ya"-nya dapat diverifikasi dalam waktu polinomial jika diberi sertifikat
3. CMasalah yang tidak dapat diselesaikan dalam waktu polinomial
4. DMasalah yang tidak dapat diselesaikan algoritma apa pun