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(n log n)
  2. BO(n)
  3. CO(log n)
  4. DO(n²)
2.Mudah

Berapa Big O dari 3n² + 5n + 2?

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

Pertumbuhan O(2ⁿ) disebut apa?

  1. ALinear
  2. BPolinomial
  3. CEksponensial
  4. DLogaritmik
4.Sedang

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Apa yang diukur oleh analisis amortisasi?

  1. ABiaya rata-rata per operasi atas urutan operasi kasus terburuk
  2. BBiaya algoritma pada input terbaik
  3. CBiaya yang diharapkan atas input acak
  4. DBiaya satu operasi yang paling mahal di mana pun dalam urutan itu
6.Sedang

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

  1. ASubmasalah yang tumpang tindih dan substruktur optimal
  2. BSatu loop saja
  3. CHanya input acak
  4. DTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
7.Sulit

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

  1. AKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
  2. BKarena n selalu kecil
  3. CKarena algoritma ini hanya berlaku untuk W = 0
  4. DW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
8.Sulit

Berapa kompleksitas waktu dari: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lakukan kerja O(1)?

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

Kunci jawaban

  1. 1. D · O(n²)
  2. 2. A · O(n²)
  3. 3. C · Eksponensial
  4. 4. B · O(1)
  5. 5. A · Biaya rata-rata per operasi atas urutan operasi kasus terburuk
  6. 6. A · Submasalah yang tumpang tindih dan substruktur optimal
  7. 7. D · W adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
  8. 8. C · O(n log n)

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