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 Big O dari 3n² + 5n + 2?

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

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

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

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

  1. AWaktu yang diperlukan pada komputer yang lambat
  2. BWaktu yang diharapkan pada input acak berukuran n
  3. CWaktu yang diperlukan pada input terkecil
  4. DWaktu maksimum yang diperlukan atas semua input berukuran n
4.Sedang

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

  1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
  2. BInsertion sort adalah O(n log n) pada kasus terburuk
  3. CInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
  4. DInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
5.Sedang

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

  1. AMinimum spanning tree dalam O(E log V)
  2. BLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)
  3. CUrutan topologis dalam O(V²)
  4. DLintasan terpendek antara semua pasangan simpul dalam O(V³)
6.Sedang

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

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

Bagaimana algoritma Bellman–Ford mendeteksi siklus berbobot negatif yang dapat dicapai dari sumber?

  1. AAlgoritma menjalankan Dijkstra dua kali dan membandingkan kedua hasil jaraknya
  2. BSetelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
  3. CAlgoritma menghitung siklus dengan depth-first search
  4. DAlgoritma memeriksa apakah ada sisi berbobot negatif
8.Sulit

Definisi kelas P manakah yang benar?

  1. AMasalah yang solusinya dapat diperiksa tetapi tidak pernah dapat ditemukan dalam waktu polinomial
  2. BMasalah yang memerlukan waktu eksponensial pada setiap komputer
  3. CMasalah yang dapat diselesaikan secara paralel
  4. DMasalah keputusan yang dapat diselesaikan algoritma deterministik dalam waktu polinomial

Kunci jawaban

  1. 1. B · O(n²)
  2. 2. B · O(V + E)
  3. 3. D · Waktu maksimum yang diperlukan atas semua input berukuran n
  4. 4. D · Insertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
  5. 5. D · Lintasan terpendek antara semua pasangan simpul dalam O(V³)
  6. 6. D · O(log n)
  7. 7. B · Setelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
  8. 8. D · Masalah keputusan yang dapat diselesaikan algoritma deterministik dalam waktu polinomial

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