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

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

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

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

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

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

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

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

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. ASAT umum pada formula dalam bentuk normal konjungtif
2. B2-SAT, dengan setiap klausa berisi paling banyak dua literal
3. CCircuit satisfiability
4. D3-SAT, dengan setiap klausa berisi tepat tiga literal

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

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