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. AMemproses tepat satu elemen per detik waktu eksekusi
  2. BHanya dapat dijalankan sekali
  3. CSelalu memerlukan tepat satu detik
  4. DWaktu eksekusinya tidak bertambah seiring ukuran input
2.Mudah

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

  1. AHeap sort
  2. BQuicksort
  3. CBubble sort
  4. DMerge sort
3.Mudah

Berapa nilai log₂ 1024?

  1. A10
  2. B12
  3. C512
  4. D32
4.Sedang

Algoritma greedy:

  1. AHanya menggunakan rekursi
  2. BMengambil pilihan terbaik secara lokal pada setiap langkah
  3. CMencoba setiap solusi yang mungkin
  4. DSelalu memberikan solusi optimal
5.Sedang

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

  1. AEksponensial
  2. BLogaritmik
  3. CLinear
  4. DKonstan
6.Sedang

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

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

Bagaimana travelling salesman problem diklasifikasikan?

  1. AMasalah ini berada di P karena algoritma Dijkstra menyelesaikannya dengan mengunjungi setiap kota satu kali
  2. BVersi keputusannya di P tetapi versi optimasinya NP-complete
  3. CMasalah ini undecidable
  4. DVersi keputusannya NP-complete dan versi optimasinya NP-hard
8.Sulit

Mengapa pencarian rata-rata pada tabel hash adalah O(1) tetapi kasus terburuknya O(n)?

  1. AFungsi hash lambat
  2. BAkses array memerlukan O(n)
  3. CKunci harus diurutkan terlebih dahulu
  4. DBanyak kunci dapat bertabrakan (collision) di bucket yang sama

Kunci jawaban

  1. 1. D · Waktu eksekusinya tidak bertambah seiring ukuran input
  2. 2. C · Bubble sort
  3. 3. A · 10
  4. 4. B · Mengambil pilihan terbaik secara lokal pada setiap langkah
  5. 5. A · Eksponensial
  6. 6. D · O(n)
  7. 7. D · Versi keputusannya NP-complete dan versi optimasinya NP-hard
  8. 8. D · Banyak kunci dapat bertabrakan (collision) di bucket yang sama

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