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

Notasi manakah yang menerangkan batas bawah pertumbuhan?

  1. Ao (o kecil)
  2. BΘ (Big Theta)
  3. CO (Big O)
  4. DΩ (Big Omega)
2.Mudah

Apakah tiga langkah algoritma bahagi dan takluk?

  1. AIsih, cari, kembali
  2. BBaca, kira, tulis
  3. CTeka, semak, ulang
  4. DBahagi, takluk, gabung
3.Mudah

Apakah kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

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

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

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

Apakah yang diukur oleh analisis teramortisasi?

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

Apakah kerumitan masa kes terburuk isihan pantas?

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

Untuk varian galas manakah peraturan tamak "ambil item mengikut susunan nilai bagi setiap berat" sentiasa memberikan jawapan optimum?

  1. AKedua-dua varian
  2. BGalas pecahan, yang itemnya boleh dipecahkan
  3. CTiada satu pun varian
  4. DGalas 0/1, yang itemnya mesti sentiasa diambil keseluruhan
8.Sukar

Algoritma pengaturcaraan dinamik Held–Karp menyelesaikan masalah jurujual kembara dengan tepat. Apakah masa larinya untuk n bandar?

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

Kunci jawapan

  1. 1. D · Ω (Big Omega)
  2. 2. D · Bahagi, takluk, gabung
  3. 3. B · O(n)
  4. 4. B · O(2ⁿ)
  5. 5. B · Kos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  6. 6. C · O(n²)
  7. 7. B · Galas pecahan, yang itemnya boleh dipecahkan
  8. 8. C · O(n² 2ⁿ)

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