Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. AQuicksort
2. BBubble sort
3. CMerge sort
4. DHeap sort

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig Theta
2. BLittle omega
3. CBig Omega
4. DBig O

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

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

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

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

1. AAlgoritma Dijkstra
2. BAlgoritma Kruskal
3. CDepth-first search (DFS)
4. DBellman–Ford diperlukan dalam semua kasus

Apa yang diukur oleh analisis amortisasi?

1. ABiaya yang diharapkan atas input acak
2. BBiaya satu operasi yang paling mahal di mana pun dalam urutan itu
3. CBiaya algoritma pada input terbaik
4. DBiaya rata-rata per operasi atas urutan operasi kasus terburuk

Masalah penghentian (halting problem) menunjukkan bahwa:

1. ABeberapa program berjalan lebih cepat di komputer yang lebih cepat, sehingga berhenti atau tidaknya bergantung pada perangkat keras
2. BTidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti
3. CLoop sebaiknya dihindari
4. DSetiap program pada akhirnya akan berhenti

Berapa biaya waktu dan ruang untuk menghitung bilangan Fibonacci ke-n dengan loop yang hanya menyimpan dua nilai terakhir?

1. AWaktu O(2ⁿ) dan ruang O(1)
2. BWaktu O(n) dan ruang O(n)
3. CWaktu O(n) dan ruang O(1)
4. DWaktu O(log n) dan ruang O(n)