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 O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

  1. A1 detik
  2. B4 detik
  3. C8 detik
  4. D2 detik
2.Mudah

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

  1. ASelalu memerlukan tepat satu detik
  2. BWaktu eksekusinya tidak bertambah seiring ukuran input
  3. CHanya dapat dijalankan sekali
  4. DMemproses tepat satu elemen per detik waktu eksekusi
4.Sedang

Berapa kompleksitas waktu kasus terburuk quicksort?

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

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

  1. ASekitar n
  2. BSekitar √n
  3. CSekitar n / 2
  4. DSekitar log₂ n
6.Sedang

Apa artinya suatu masalah memiliki optimal substructure?

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

Suatu masalah disebut NP-complete jika masalah tersebut:

  1. ATermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
  2. BDapat diselesaikan dalam waktu polinomial
  3. CBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
  4. DTidak mungkin diselesaikan
8.Sulit

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(V³)
  4. DO((V + E) log V)

Kunci jawaban

  1. 1. B · 4 detik
  2. 2. B · O(2ⁿ)
  3. 3. B · Waktu eksekusinya tidak bertambah seiring ukuran input
  4. 4. D · O(n²)
  5. 5. D · Sekitar log₂ n
  6. 6. C · Solusi optimal dapat dibangun dari solusi optimal submasalahnya
  7. 7. A · Termasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
  8. 8. D · O((V + E) log V)

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