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²)
  4. DO(n log n)
2.Mudah

Notasi manakah yang menerangkan batas atas pertumbuhan?

  1. ABig Omega
  2. BBig O
  3. CBig Theta
  4. DOmega kecil
3.Mudah

Apakah yang diperlukan oleh carian binari daripada inputnya?

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

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

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

Algoritma tamak (greedy):

  1. AMembuat pilihan terbaik setempat pada setiap langkah
  2. BMencuba setiap penyelesaian yang mungkin
  3. CSentiasa memberikan penyelesaian optimum
  4. DHanya menggunakan rekursi
6.Sederhana

Isihan pantas sentiasa menggunakan elemen pertama sebagai pangsi. Pada input manakah ia menunjukkan tingkah laku kes terburuk?

  1. ATatasusunan yang sudah tersusun
  2. BTatasusunan yang semua elemennya berbeza
  3. CTatasusunan sepanjang 2
  4. DTatasusunan dalam susunan rawak
7.Sukar

Apakah kos teramortisasi menokok pembilang binari, memandangkan satu tokokan boleh membalikkan banyak bit?

  1. AO(n) bagi setiap tokokan
  2. BO(1) bagi setiap tokokan
  3. CO(log n) bagi setiap tokokan
  4. DO(n log n) bagi setiap tokokan
8.Sukar

Mengapakah sebarang carian berasaskan perbandingan dalam tatasusunan tersusun memerlukan Ω(log n) perbandingan dalam kes terburuk?

  1. ASetiap elemen mesti dibandingkan sekurang-kurangnya sekali
  2. BCarian binari ialah satu-satunya algoritma yang mungkin, dan ia memerlukan log₂ n perbandingan
  3. CPerbandingan mengambil masa logaritma setiap satu
  4. DPokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n

Kunci jawapan

  1. 1. A · O(2ⁿ)
  2. 2. B · Big O
  3. 3. B · Tatasusunan mestilah tersusun
  4. 4. D · Pilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
  5. 5. A · Membuat pilihan terbaik setempat pada setiap langkah
  6. 6. A · Tatasusunan yang sudah tersusun
  7. 7. B · O(1) bagi setiap tokokan
  8. 8. D · Pokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n

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