Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan rekursi?

1. ASejenis struktur data
2. BFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil
3. CSebuah metode pengurutan
4. DLoop yang tidak pernah berakhir

Bagaimana cara kerja selection sort?

1. ABerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
2. BBerulang kali menukar elemen bersebelahan yang urutannya salah
3. CMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
4. DMembagi array menjadi dua bagian lalu menggabungkannya

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu yang diharapkan atas distribusi input berukuran n tertentu
2. BWaktu pada komputer yang paling umum
3. CNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
4. DWaktu untuk input dengan panjang rata-rata

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

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

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. ALintasan terpendek antara semua pasangan simpul dalam O(V³)
2. BUrutan topologis dalam O(V²)
3. CLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)
4. DMinimum spanning tree dalam O(E log V)

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

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

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

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

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

1. AΘ(n log n)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n³)