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

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

  1. AMemproses tepat satu elemen per detik waktu eksekusi
  2. BWaktu eksekusinya tidak bertambah seiring ukuran input
  3. CHanya dapat dijalankan sekali
  4. DSelalu memerlukan tepat satu detik
3.Mudah

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

  1. ATidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
  2. BTidak, karena n³ lebih kecil daripada n² untuk n besar
  3. CYa, tetapi hanya jika n lebih kecil dari 100
  4. DYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
5.Sedang

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

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

Bagaimana algoritma Prim membangun minimum spanning tree?

  1. AMenjalankan breadth-first search dan menyimpan pohon BFS
  2. BMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
  3. CMenghapus sisi termahal sampai tidak ada siklus tersisa
  4. DMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
7.Sulit

Masalah penghentian (halting problem) menunjukkan bahwa:

  1. ASetiap program pada akhirnya akan berhenti
  2. BTidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti
  3. CBeberapa program berjalan lebih cepat di komputer yang lebih cepat, sehingga berhenti atau tidaknya bergantung pada perangkat keras
  4. DLoop sebaiknya dihindari
8.Sulit

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

  1. AKualitasnya tidak diketahui dibandingkan optimum
  2. BPaling banyak log n kali minimum
  3. CSelalu merupakan minimum vertex cover
  4. DPaling banyak dua kali ukuran minimum vertex cover

Kunci jawaban

  1. 1. D · O(n²)
  2. 2. B · Waktu eksekusinya tidak bertambah seiring ukuran input
  3. 3. C · O(1)
  4. 4. D · Ya, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
  5. 5. C · O(n²)
  6. 6. B · Menumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
  7. 7. B · Tidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti
  8. 8. D · Paling banyak dua kali ukuran minimum vertex cover

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