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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Pertumbuhan O(2ⁿ) disebut apa?

  1. APolinomial
  2. BEksponensial
  3. CLinear
  4. DLogaritmik
3.Mudah

Manakah dari waktu eksekusi berikut yang polinomial?

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Algoritma pengurutan manakah yang stabil (stable)?

  1. AMerge sort
  2. BQuicksort (versi in-place yang umum)
  3. CHeap sort
  4. DSelection sort (versi yang umum)
7.Sulit

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

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

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

  1. AFractional knapsack, ketika item boleh dipecah
  2. B0/1 knapsack, ketika item harus selalu diambil utuh
  3. CTidak ada varian
  4. DKedua varian

Kunci jawaban

  1. 1. D · O(n²)
  2. 2. B · Eksponensial
  3. 3. B · O(n³)
  4. 4. B · O(d(n + k))
  5. 5. D · O(n)
  6. 6. A · Merge sort
  7. 7. A · X berada di NP, dan masalah NP-complete yang sudah dikenal dapat direduksi ke X dalam waktu polinomial
  8. 8. A · Fractional knapsack, ketika item boleh dipecah

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