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

Kelas kerumitan manakah yang tumbuh paling pantas untuk n yang besar?

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

Apakah yang diperlukan oleh carian binari daripada inputnya?

  1. ATatasusunan mestilah tersusun
  2. BTatasusunan tidak boleh mempunyai lebih daripada 1000 elemen
  3. CTatasusunan mesti mengandungi nombor positif sahaja
  4. DPanjang tatasusunan mestilah kuasa dua
3.Mudah

Apakah algoritma?

  1. AMana-mana program komputer yang mempunyai antara muka grafik
  2. BJujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
  3. CStruktur data yang menyimpan nombor
  4. DBahasa pengaturcaraan yang direka untuk menulis formula matematik
4.Sederhana

Dalam masalah pemilihan aktiviti, peraturan tamak manakah yang sentiasa memberikan bilangan maksimum aktiviti yang tidak bertindih?

  1. APilih aktiviti yang bermula paling awal
  2. BPilih aktiviti dengan pertindihan paling sedikit dahulu, kemudian ulang dengan yang serasi
  3. CPilih aktiviti terpendek dahulu
  4. DPilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
5.Sederhana

Apakah penyelesaian hubungan jadi semula T(n) = T(n − 1) + O(n)?

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

Mengapakah asas logaritma biasanya ditinggalkan dalam Big O, seperti dalam O(log n)?

  1. ALogaritma dengan asas berbeza hanya berbeza oleh faktor malar
  2. BAsas hanya penting untuk n yang kecil
  3. CSemua logaritma dalam sains komputer berasas 10, jadi ia tersirat
  4. DLogaritma sentiasa dibundarkan kepada integer
7.Sukar

Bagaimanakah n! dan 2ⁿ dibandingkan untuk n yang besar?

  1. An! ialah O(n²)
  2. B2ⁿ tumbuh lebih pantas daripada n!
  3. Cn! tumbuh lebih pantas daripada 2ⁿ
  4. DKeduanya tumbuh pada kadar yang sama
8.Sukar

Pernyataan manakah tentang memilih elemen terkecil ke-k dalam tatasusunan tidak tersusun yang betul?

  1. AQuickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk
  2. BPemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan
  3. CQuickselect berjalan dalam O(log n) kes terburuk, kerana ia berekursi pada satu sebelah pangsi sahaja
  4. DPemilihan hanya mungkin dalam O(n²)

Kunci jawapan

  1. 1. A · O(2ⁿ)
  2. 2. A · Tatasusunan mestilah tersusun
  3. 3. B · Jujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
  4. 4. D · Pilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
  5. 5. D · O(n²)
  6. 6. A · Logaritma dengan asas berbeza hanya berbeza oleh faktor malar
  7. 7. C · n! tumbuh lebih pantas daripada 2ⁿ
  8. 8. A · Quickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk

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