Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. AHeap sort
2. BBubble sort
3. CMerge sort
4. DQuicksort

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Bagaimana algoritma Prim membangun minimum spanning tree?

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

Rekurens T(n) = T(n − 1) + O(1) menghasilkan apa?

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

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. ASetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
2. BHanya masalah itu yang pindah ke P
3. CHalting problem menjadi decidable
4. DSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. AMasalah itu undecidable
2. BDapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan
3. CSelalu dapat diselesaikan dalam O(V + E)
4. DMasalah itu NP-hard