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 banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

  1. ALinear
  2. BKuadratik
  3. CKonstan
  4. DLogaritmik
3.Mudah

Pertumbuhan O(2ⁿ) disebut apa?

  1. ALogaritmik
  2. BLinear
  3. CEksponensial
  4. DPolinomial
4.Sedang

Berapa kompleksitas waktu dari: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

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

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

Apa yang ditetapkan oleh teorema Cook–Levin?

  1. AP tidak sama dengan NP
  2. BBoolean satisfiability problem (SAT) adalah NP-complete
  3. CHalting problem tidak dapat diputuskan (undecidable)
  4. DSetiap masalah NP dapat diselesaikan dalam waktu eksponensial
8.Sulit

Algoritma Strassen mengalikan matriks memakai 7, bukan 8, perkalian rekursif blok berukuran setengah. Berapa waktu eksekusinya?

  1. AΘ(n³)
  2. BΘ(nlog₂ 7), sekitar n2,81
  3. CΘ(n² log n)
  4. DΘ(n2)

Kunci jawaban

  1. 1. A · O(n)
  2. 2. A · Linear
  3. 3. C · Eksponensial
  4. 4. A · O(n log n)
  5. 5. B · O(n)
  6. 6. A · O(V × E)
  7. 7. B · Boolean satisfiability problem (SAT) adalah NP-complete
  8. 8. B · Θ(nlog₂ 7), sekitar n2,81

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