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

Manakah dari waktu eksekusi berikut yang polinomial?

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

Suatu masalah biasanya disebut tractable jika:

  1. AHanya dapat diselesaikan dengan mencoba setiap kemungkinan
  2. BDapat diselesaikan dalam waktu konstan
  3. CTidak memiliki solusi
  4. DDapat diselesaikan dalam waktu polinomial
3.Mudah

Berapa nilai log₂ 1024?

  1. A512
  2. B32
  3. C12
  4. D10
4.Sedang

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

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

Breadth-first search (BFS) pada graf tak berbobot menemukan:

  1. AUrutan topologis pada semua graf
  2. BLintasan terpendek berdasarkan jumlah sisi dari simpul awal
  3. CLintasan terpendek pada graf yang memiliki bobot sisi negatif
  4. DPohon rentang minimum
6.Sedang

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

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

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

  1. AMenggunakan rekursi hanya pada sisi kiri
  2. BMengurutkan input sebelum menjalankan quicksort
  3. CMemilih pivot secara acak seragam
  4. DSelalu memilih elemen pertama
8.Sulit

Pengurutan topologis hanya mungkin dilakukan untuk:

  1. AGraf dengan bobot negatif
  2. BGraf berarah asiklik (DAG)
  3. CGraf tak berarah
  4. DGraf lengkap

Kunci jawaban

  1. 1. A · O(n³)
  2. 2. D · Dapat diselesaikan dalam waktu polinomial
  3. 3. D · 10
  4. 4. C · Sekitar log₂ n
  5. 5. B · Lintasan terpendek berdasarkan jumlah sisi dari simpul awal
  6. 6. A · O(n)
  7. 7. C · Memilih pivot secara acak seragam
  8. 8. B · Graf berarah asiklik (DAG)

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