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 yang diperlukan oleh carian binari daripada inputnya?

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

Apakah tiga langkah algoritma bahagi dan takluk?

  1. ABaca, kira, tulis
  2. BTeka, semak, ulang
  3. CBahagi, takluk, gabung
  4. DIsih, cari, kembali
3.Mudah

Apakah kerumitan masa kes terburuk isihan sisipan?

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

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

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

Algoritma isihan manakah yang stabil?

  1. AIsihan cantum
  2. BIsihan pemilihan (versi biasa)
  3. CIsihan timbunan
  4. DIsihan pantas (versi dalam-tempat biasa)
6.Sederhana

Carian pertama lebar pada graf tidak berpemberat mencari:

  1. APokok rentang minimum
  2. BLaluan terpendek dalam graf yang mengandungi pemberat sisi negatif
  3. CLaluan terpendek dari segi bilangan sisi dari nod permulaan
  4. DSusunan topologi dalam semua graf
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

Menggunakan teorem induk, T(n) = 8T(n/2) + O(n²) mempunyai penyelesaian:

  1. AΘ(n³)
  2. BΘ(n²)
  3. CΘ(n² log n)
  4. DΘ(n log n)

Kunci jawapan

  1. 1. B · Tatasusunan mestilah tersusun
  2. 2. C · Bahagi, takluk, gabung
  3. 3. D · O(n²)
  4. 4. B · O(log n)
  5. 5. A · Isihan cantum
  6. 6. C · Laluan terpendek dari segi bilangan sisi dari nod permulaan
  7. 7. B · O(1) bagi setiap tokokan
  8. 8. A · Θ(n³)

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