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

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

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

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

  1. ABig Omega
  2. BBig Theta
  3. CBig O
  4. DLittle omega
3.Mudah

Strategi desain apa yang digunakan merge sort?

  1. APilihan greedy
  2. BBrute force
  3. CDynamic programming
  4. DDivide and conquer (bagi dan taklukkan)
4.Sedang

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

  1. ASemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
  2. BLogaritma selalu dibulatkan menjadi bilangan bulat
  3. CLogaritma dengan basis berbeda hanya berbeda faktor konstan
  4. DBasis hanya berpengaruh untuk n kecil
6.Sedang

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

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

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

  1. AO((V + E) log V)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V³)
8.Sulit

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

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

Kunci jawaban

  1. 1. A · Waktu maksimum yang diperlukan atas semua input berukuran n
  2. 2. C · Big O
  3. 3. D · Divide and conquer (bagi dan taklukkan)
  4. 4. A · O(n)
  5. 5. C · Logaritma dengan basis berbeda hanya berbeda faktor konstan
  6. 6. C · Insertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
  7. 7. A · O((V + E) log V)
  8. 8. D · W adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W

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