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 pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

  1. ABubble sort
  2. BHeap sort
  3. CQuicksort
  4. DMerge sort
2.Mudah

Manakah dari waktu eksekusi berikut yang polinomial?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
3.Mudah

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

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

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

  1. AArray dalam urutan acak
  2. BArray dengan panjang 2
  3. CArray yang sudah terurut
  4. DArray yang semua elemennya berbeda
5.Sedang

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

  1. ASatu loop saja
  2. BTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
  3. CHanya input acak
  4. DSubmasalah yang tumpang tindih dan substruktur optimal
6.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 4 koin; optimalnya 3
  2. BGreedy memakai 3 koin; optimalnya 2
  3. CGreedy memakai 3 koin; optimalnya 3
  4. DGreedy memakai 2 koin; optimalnya 2
7.Sulit

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

  1. APaling banyak log n kali minimum
  2. BPaling banyak dua kali ukuran minimum vertex cover
  3. CKualitasnya tidak diketahui dibandingkan optimum
  4. DSelalu merupakan minimum vertex cover
8.Sulit

Algoritma dynamic programming Held–Karp menyelesaikan travelling salesman problem secara eksak. Berapa waktu eksekusinya untuk n kota?

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

Kunci jawaban

  1. 1. A · Bubble sort
  2. 2. C · O(n³)
  3. 3. C · O(n²)
  4. 4. C · Array yang sudah terurut
  5. 5. D · Submasalah yang tumpang tindih dan substruktur optimal
  6. 6. B · Greedy memakai 3 koin; optimalnya 2
  7. 7. B · Paling banyak dua kali ukuran minimum vertex cover
  8. 8. C · O(n² 2ⁿ)

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