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

Bagaimanakah isihan pemilihan berfungsi?

  1. AIa menyisipkan setiap elemen ke dalam bahagian tersusun yang berkembang dengan menganjak
  2. BIa membahagikan tatasusunan kepada dua dan mencantumkannya
  3. CIa berulang kali mencari minimum bahagian tidak tersusun dan menukarnya ke hadapan
  4. DIa berulang kali menukar elemen jiran yang berada dalam susunan salah
2.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
3.Mudah

Algoritma dengan dua gelung bersarang, masing-masing berjalan n kali, biasanya mempunyai kerumitan yang mana?

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

Batas bawah bagi isihan berasaskan perbandingan dalam kes terburuk ialah:

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n²)
5.Sederhana

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

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

Algoritma manakah yang mencari laluan terpendek dari satu sumber dalam graf dengan pemberat sisi tidak negatif?

  1. ABellman–Ford diperlukan dalam semua kes
  2. BAlgoritma Dijkstra
  3. CCarian pertama dalam
  4. DAlgoritma Kruskal
7.Sukar

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

  1. AGalas 0/1, yang itemnya mesti sentiasa diambil keseluruhan
  2. BKedua-dua varian
  3. CGalas pecahan, yang itemnya boleh dipecahkan
  4. DTiada satu pun varian
8.Sukar

Batas manakah yang betul untuk log(n!)?

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

Kunci jawapan

  1. 1. C · Ia berulang kali mencari minimum bahagian tidak tersusun dan menukarnya ke hadapan
  2. 2. B · Jujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
  3. 3. B · O(n²)
  4. 4. A · Ω(n log n)
  5. 5. A · O(log n)
  6. 6. B · Algoritma Dijkstra
  7. 7. C · Galas pecahan, yang itemnya boleh dipecahkan
  8. 8. C · Θ(n log n)

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