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

Bagaimana cara kerja selection sort?

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

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

  1. A6 detik
  2. B12 detik
  3. C3 detik
  4. D9 detik
3.Mudah

Apa tiga langkah algoritma divide and conquer?

  1. ATebak, periksa, ulangi
  2. BDivide, conquer, combine (bagi, taklukkan, gabungkan)
  3. CBaca, hitung, tulis
  4. DUrutkan, cari, kembalikan
4.Sedang

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

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

Algoritma greedy:

  1. ASelalu memberikan solusi optimal
  2. BMengambil pilihan terbaik secara lokal pada setiap langkah
  3. CHanya menggunakan rekursi
  4. DMencoba setiap solusi yang mungkin
6.Sedang

Apa artinya suatu masalah memiliki optimal substructure?

  1. ASolusi optimal dapat dibangun dari solusi optimal submasalahnya
  2. BMasalah itu dapat diselesaikan dalam waktu konstan
  3. CSetiap submasalah memiliki ukuran yang sama
  4. DMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
7.Sulit

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

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

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

  1. AKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
  2. BKarena algoritma ini hanya berlaku untuk W = 0
  3. CW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
  4. DKarena n selalu kecil

Kunci jawaban

  1. 1. C · Berulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
  2. 2. A · 6 detik
  3. 3. B · Divide, conquer, combine (bagi, taklukkan, gabungkan)
  4. 4. B · O(n²)
  5. 5. B · Mengambil pilihan terbaik secara lokal pada setiap langkah
  6. 6. A · Solusi optimal dapat dibangun dari solusi optimal submasalahnya
  7. 7. C · Θ(n log² n)
  8. 8. C · W adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W

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