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 kerumitan masa kes terburuk isihan cantum?

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

Apakah yang diterangkan oleh masa larian kes purata?

  1. AMasa pada komputer yang paling biasa
  2. BNilai tengah antara masa larian kes terbaik dan kes terburuk
  3. CMasa dijangka merentasi taburan input tertentu bersaiz n
  4. DMasa untuk input dengan panjang purata
3.Mudah

Apakah algoritma?

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

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

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

Apakah kerumitan masa kes terburuk isihan pantas?

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

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

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

Mengambil kedua-dua hujung setiap sisi dalam padanan maksimal memberikan litupan bucu. Sebaik manakah litupan ini?

  1. AMutunya tidak diketahui berbanding optimum
  2. BSentiasa litupan bucu minimum
  3. CPaling banyak dua kali ganda saiz litupan bucu minimum
  4. DPaling banyak log n kali minimum
8.Sukar

Pernyataan manakah tentang notasi o kecil yang betul?

  1. A2n = o(n), kerana 2n tumbuh perlahan
  2. Bn = o(n²), tetapi n bukan o(n)
  3. Cn = o(n), kerana setiap fungsi ialah o kecil bagi dirinya sendiri
  4. Dn² = o(n)

Kunci jawapan

  1. 1. C · O(n log n)
  2. 2. C · Masa dijangka merentasi taburan input tertentu bersaiz n
  3. 3. B · Jujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
  4. 4. D · Logaritma dengan asas berbeza hanya berbeza oleh faktor malar
  5. 5. B · O(n²)
  6. 6. B · O(n)
  7. 7. C · Paling banyak dua kali ganda saiz litupan bucu minimum
  8. 8. B · n = o(n²), tetapi n bukan o(n)

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