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 untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

  1. ASekitar n²
  2. BSekitar n
  3. CSekitar n / 2
  4. DSekitar log₂ n
3.Mudah

Algoritma O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

  1. A4 detik
  2. B8 detik
  3. C2 detik
  4. D1 detik
4.Sedang

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

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

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

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

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

  1. AO(n²)
  2. BO(1)
  3. CO(n)
  4. DO(log n)
7.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) log V)
  3. CO(V³)
  4. DO(V × E)
8.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. BBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
  3. CTidak mungkin diselesaikan
  4. DDapat diselesaikan dalam waktu polinomial

Kunci jawaban

  1. 1. C · O(n)
  2. 2. D · Sekitar log₂ n
  3. 3. A · 4 detik
  4. 4. D · O(V × E)
  5. 5. A · O(log n)
  6. 6. C · O(n)
  7. 7. B · O((V + E) log V)
  8. 8. A · Termasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial

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