Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud base case pada fungsi rekursif?

1. AKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
2. BPemanggilan yang memakai memori paling banyak
3. CKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
4. DBaris pertama fungsi

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang mencoba semua kandidat solusi yang mungkin
2. BAlgoritma yang menebak jawaban secara acak
3. CAlgoritma yang selalu memakai rekursi
4. DAlgoritma yang berjalan di banyak prosesor

Berapa Big O dari 3n² + 5n + 2?

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

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

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

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

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

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

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

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

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

Dua hal apa yang harus ditunjukkan untuk membuktikan bahwa masalah keputusan X adalah NP-complete?

1. AX berada di P, dan X dapat direduksi ke SAT
2. BX dapat direduksi ke masalah di P, dan X berada di NP
3. CX berada di NP, dan masalah NP-complete yang sudah dikenal dapat direduksi ke X dalam waktu polinomial
4. DX tidak memiliki algoritma polinomial, dan X decidable