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

Yang manakah tumbuh paling perlahan apabila n menjadi besar?

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

Apakah kerumitan masa kes terburuk isihan sisipan?

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

Apakah kerumitan masa kes terburuk isihan cantum?

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

Apakah kerumitan masa mendarab dua matriks n × n dengan tiga gelung piawai?

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

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

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

Berapa banyak ruang tindanan yang digunakan oleh fungsi faktorial rekursif mudah fact(n) = n × fact(n − 1)?

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

Masalah penghentian (halting problem) menunjukkan bahawa:

  1. AGelung harus dielakkan
  2. BSesetengah program berjalan lebih pantas pada komputer yang lebih pantas, jadi penghentian bergantung pada perkakasan
  3. CSetiap program akhirnya berhenti
  4. DTiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti
8.Sukar

Takrifan kelas P yang manakah betul?

  1. AMasalah yang penyelesaiannya boleh disemak tetapi tidak pernah dapat dicari dalam masa polinomial
  2. BMasalah yang boleh diselesaikan secara selari
  3. CMasalah yang memerlukan masa eksponen pada setiap komputer
  4. DMasalah keputusan yang boleh diselesaikan oleh algoritma deterministik dalam masa polinomial

Kunci jawapan

  1. 1. C · O(log n)
  2. 2. A · O(n²)
  3. 3. C · O(n log n)
  4. 4. C · O(n³)
  5. 5. B · O(n²)
  6. 6. A · O(n)
  7. 7. D · Tiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti
  8. 8. D · Masalah keputusan yang boleh diselesaikan oleh algoritma deterministik dalam masa polinomial

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