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

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

  1. Ao (little o)
  2. BΘ (Big Theta)
  3. CO (Big O)
  4. DΩ (Big Omega)
3.Mudah

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

  1. AQuicksort
  2. BBubble sort
  3. CHeap sort
  4. DMerge sort
4.Sedang

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

  1. AO(k n log n)
  2. BO(nk)
  3. CO(n log n + k log n)
  4. DO(n + k)
5.Sedang

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

  1. AGreedy memakai 3 koin; optimalnya 3
  2. BGreedy memakai 3 koin; optimalnya 2
  3. CGreedy memakai 2 koin; optimalnya 2
  4. DGreedy memakai 4 koin; optimalnya 3
6.Sedang

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

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

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

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

Bagaimana perbandingan n! dan 2ⁿ untuk n besar?

  1. An! tumbuh lebih cepat daripada 2ⁿ
  2. B2ⁿ tumbuh lebih cepat daripada n!
  3. CKeduanya tumbuh dengan laju yang sama
  4. Dn! adalah O(n²)

Kunci jawaban

  1. 1. B · O(n²)
  2. 2. D · Ω (Big Omega)
  3. 3. B · Bubble sort
  4. 4. C · O(n log n + k log n)
  5. 5. B · Greedy memakai 3 koin; optimalnya 2
  6. 6. D · O(n)
  7. 7. D · Θ(n³)
  8. 8. A · n! tumbuh lebih cepat daripada 2ⁿ

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