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 untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Apa yang dimaksud dengan algoritma?

  1. AStruktur data yang menyimpan bilangan
  2. BSetiap program komputer yang memiliki antarmuka grafis
  3. CBahasa pemrograman yang dirancang untuk menulis rumus matematika
  4. DUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah
3.Mudah

Apa yang dimaksud dengan memoisasi?

  1. AMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
  2. BMembebaskan memori setelah fungsi selesai
  3. CMenulis komentar di samping setiap baris kode
  4. DMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
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

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

  1. ALogaritmik
  2. BLinear
  3. CKonstan
  4. DEksponensial
7.Sulit

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

  1. AMenunjukkan bahwa X dapat diverifikasi 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. DMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
8.Sulit

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

  1. ABinary search memerlukan setidaknya dua kali lipat memori
  2. BLinked list tidak dapat diurutkan
  3. CMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung
  4. DPerbandingan pada node linked list lebih lambat

Kunci jawaban

  1. 1. C · O(n)
  2. 2. D · Urutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah
  3. 3. D · Menyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
  4. 4. D · Insertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
  5. 5. B · O(n log n)
  6. 6. D · Eksponensial
  7. 7. B · Mereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
  8. 8. C · Mencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung

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