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 merge sort?

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

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

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

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

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

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

Algoritma greedy:

  1. ASelalu memberikan solusi optimal
  2. BMencoba setiap solusi yang mungkin
  3. CHanya menggunakan rekursi
  4. DMengambil pilihan terbaik secara lokal pada setiap langkah
7.Sulit

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

  1. AMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
  2. BMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
  3. CMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
  4. DMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
8.Sulit

Suatu masalah disebut NP-complete jika masalah tersebut:

  1. ABerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
  2. BTidak mungkin diselesaikan
  3. CDapat diselesaikan dalam waktu polinomial
  4. DTermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial

Kunci jawaban

  1. 1. A · O(n log n)
  2. 2. D · O(V + E)
  3. 3. B · O(n²)
  4. 4. A · O(n³)
  5. 5. A · O(d(n + k))
  6. 6. D · Mengambil pilihan terbaik secara lokal pada setiap langkah
  7. 7. B · Mereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
  8. 8. D · 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.