Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

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

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

Bagaimana cara kerja selection sort?

1. AMembagi array menjadi dua bagian lalu menggabungkannya
2. BMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
3. CBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
4. DBerulang kali menukar elemen bersebelahan yang urutannya salah

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ALogaritma dengan basis berbeda hanya berbeda faktor konstan
2. BBasis hanya berpengaruh untuk n kecil
3. CSemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
4. DLogaritma selalu dibulatkan menjadi bilangan bulat

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. AAlgoritma Kruskal
2. BBellman–Ford diperlukan dalam semua kasus
3. CAlgoritma Dijkstra
4. DDepth-first search (DFS)

Untuk varian knapsack mana aturan greedy "ambil item berdasarkan urutan nilai per berat" selalu memberikan jawaban optimal?

1. ATidak ada varian
2. BFractional knapsack, ketika item boleh dipecah
3. CKedua varian
4. D0/1 knapsack, ketika item harus selalu diambil utuh

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. AQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot
2. BSeleksi hanya mungkin dilakukan dalam O(n²)
3. CSeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
4. DQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk