Lembar kerja Algoritma & kompleksitas dengan jawaban

Lembar kerja Algoritma & kompleksitas gratis yang dapat dicetak: 8 soal dari mudah hingga tingkat ujian, dengan kunci jawaban. Cetak atau simpan sebagai PDF.

Lembar kerja baruBerlatih online dengan petunjuk

Untuk pengajar: gratis untuk dicetak, disalin, dan dipakai di kelas. Setiap lembar kerja baru punya nilai baru dan kunci jawabannya sendiri. Tautan ke ExamProblems di halaman mata kuliah Anda sangat kami hargai.

Nama: ____________________   Tanggal: ____________

1.Mudah

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

  1. ASelalu memerlukan tepat satu detik
  2. BHanya dapat dijalankan sekali
  3. CWaktu eksekusinya tidak bertambah seiring ukuran input
  4. DMemproses tepat satu elemen per detik waktu eksekusi
2.Mudah

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

  1. ASekitar n²
  2. BSekitar n
  3. CSekitar log₂ n
  4. DSekitar n / 2
3.Mudah

Apa yang dimaksud base case pada fungsi rekursif?

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

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

  1. ASatu loop saja
  2. BSubmasalah yang tumpang tindih dan substruktur optimal
  3. CTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
  4. DHanya input acak
5.Sedang

Apa artinya suatu masalah memiliki optimal substructure?

  1. AMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
  2. BSolusi optimal dapat dibangun dari solusi optimal submasalahnya
  3. CSetiap submasalah memiliki ukuran yang sama
  4. DMasalah itu dapat diselesaikan dalam waktu konstan
6.Sedang

Apa yang diukur oleh analisis amortisasi?

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

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

  1. AMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
  2. BMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
  3. CMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
  4. DMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
8.Sulit

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

  1. AKedua varian
  2. BTidak ada varian
  3. CFractional knapsack, ketika item boleh dipecah
  4. D0/1 knapsack, ketika item harus selalu diambil utuh

Kunci jawaban

  1. 1. C · Waktu eksekusinya tidak bertambah seiring ukuran input
  2. 2. C · Sekitar log₂ n
  3. 3. C · Kasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
  4. 4. B · Submasalah yang tumpang tindih dan substruktur optimal
  5. 5. B · Solusi optimal dapat dibangun dari solusi optimal submasalahnya
  6. 6. B · Biaya rata-rata per operasi atas urutan operasi kasus terburuk
  7. 7. C · Mereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
  8. 8. C · Fractional knapsack, ketika item boleh dipecah

Penyelesaian lengkap langkah demi langkah: latih topik ini di examproblems.com.