Lembaran kerja Algoritma & kerumitan dengan jawapan

Lembaran kerja Algoritma & kerumitan percuma untuk dicetak: 8 soalan dari mudah hingga tahap peperiksaan, dengan skema jawapan. Cetak atau simpan sebagai PDF.

Lembaran kerja baharuBerlatih dalam talian dengan petunjuk

Untuk pensyarah dan guru: percuma untuk dicetak, disalin dan digunakan di dalam kelas. Setiap lembaran kerja baharu mempunyai nilai baharu dan skema jawapannya sendiri. Pautan ke ExamProblems di halaman kursus anda amat dihargai.

Nama: ____________________   Tarikh: ____________

1.Mudah

Apakah tiga langkah algoritma bahagi dan takluk?

  1. ABahagi, takluk, gabung
  2. BTeka, semak, ulang
  3. CIsih, cari, kembali
  4. DBaca, kira, tulis
2.Mudah

Notasi manakah yang menerangkan batas atas pertumbuhan?

  1. ABig Omega
  2. BOmega kecil
  3. CBig O
  4. DBig Theta
3.Mudah

Algoritma isihan manakah yang berulang kali menukar elemen bersebelahan yang berada dalam susunan yang salah?

  1. AIsihan timbunan
  2. BIsihan cantum
  3. CIsihan pantas
  4. DIsihan gelembung
4.Sederhana

Apakah yang diukur oleh analisis teramortisasi?

  1. AKos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  2. BKos satu operasi yang paling mahal di mana-mana dalam jujukan itu
  3. CKos algoritma pada input terbaik
  4. DKos dijangka merentasi input rawak
5.Sederhana

Berapa banyak peringkat yang ada pada rekursi isihan cantum bagi tatasusunan n elemen?

  1. AKira-kira n
  2. BKira-kira log₂ n
  3. CKira-kira n / 2
  4. DKira-kira √n
6.Sederhana

Mengapakah banyak rutin isihan pustaka bertukar kepada isihan sisipan untuk subtatasusunan yang sangat kecil?

  1. AIsihan sisipan menggunakan memori lebih sedikit daripada mana-mana algoritma pengisihan lain pada input besar
  2. BIsihan sisipan ialah O(n log n) dalam kes terburuk
  3. CIsihan sisipan mempunyai overhed yang rendah dan pantas pada input kecil atau hampir tersusun
  4. DAlgoritma rekursif tidak boleh mengendalikan tatasusunan di bawah 10 elemen
7.Sukar

Apakah yang akan menyusul jika seseorang menemui algoritma masa polinomial untuk satu masalah NP-lengkap?

  1. AHanya satu masalah itu berpindah ke dalam P
  2. BMasalah penghentian menjadi boleh diputuskan
  3. CSemua algoritma masa eksponen serta-merta berjalan dalam masa linear
  4. DSetiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
8.Sukar

Masalah penghentian (halting problem) menunjukkan bahawa:

  1. ASesetengah program berjalan lebih pantas pada komputer yang lebih pantas, jadi penghentian bergantung pada perkakasan
  2. BSetiap program akhirnya berhenti
  3. CGelung harus dielakkan
  4. DTiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti

Kunci jawapan

  1. 1. A · Bahagi, takluk, gabung
  2. 2. C · Big O
  3. 3. D · Isihan gelembung
  4. 4. A · Kos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  5. 5. B · Kira-kira log₂ n
  6. 6. C · Isihan sisipan mempunyai overhed yang rendah dan pantas pada input kecil atau hampir tersusun
  7. 7. D · Setiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
  8. 8. D · Tiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti

Penyelesaian langkah demi langkah yang lengkap: berlatih topik ini di examproblems.com.