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

Kelas kerumitan manakah yang tumbuh paling pantas untuk n yang besar?

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

Apakah pertumbuhan O(2ⁿ) dipanggil?

  1. ALinear
  2. BPolinomial
  3. CLogaritma
  4. DEksponen
3.Mudah

Apakah log₂ 1024?

  1. A12
  2. B10
  3. C512
  4. D32
4.Sederhana

Sesuatu fungsi menjalankan satu gelung n lelaran dan kemudian, secara berasingan, satu lagi gelung n lelaran. Apakah kerumitan masanya?

  1. AO(2ⁿ)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
5.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
6.Sederhana

Apakah kerumitan masa mengira nombor Fibonacci ke-n dengan jadual bawah-atas?

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

Pernyataan manakah tentang memilih elemen terkecil ke-k dalam tatasusunan tidak tersusun yang betul?

  1. AQuickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk
  2. BPemilihan hanya mungkin dalam O(n²)
  3. CQuickselect berjalan dalam O(log n) kes terburuk, kerana ia berekursi pada satu sebelah pangsi sahaja
  4. DPemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan
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² 2ⁿ)
  3. CO(2n²)
  4. DO(n!)

Kunci jawapan

  1. 1. C · O(2ⁿ)
  2. 2. D · Eksponen
  3. 3. B · 10
  4. 4. C · O(n)
  5. 5. B · Algoritma Dijkstra
  6. 6. D · O(n)
  7. 7. A · Quickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk
  8. 8. B · O(n² 2ⁿ)

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