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. BO (Big O)
  3. CΩ (Big Omega)
  4. DΘ (Big Theta)
2.Mudah

Apakah Big O bagi 3n² + 5n + 2?

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

Apakah kerumitan masa kes terburuk isihan sisipan?

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

Apakah kerumitan masa algoritma Bellman–Ford pada graf dengan V bucu dan E sisi?

  1. AO(V + E)
  2. BO(V³ × E)
  3. CO(V × E)
  4. DO(E log V)
5.Sederhana

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

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

Dalam masalah pemilihan aktiviti, peraturan tamak manakah yang sentiasa memberikan bilangan maksimum aktiviti yang tidak bertindih?

  1. APilih aktiviti yang bermula paling awal
  2. BPilih aktiviti terpendek dahulu
  3. CPilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
  4. DPilih aktiviti dengan pertindihan paling sedikit dahulu, kemudian ulang dengan yang serasi
7.Sukar

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

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

Batas manakah yang betul untuk log(n!)?

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

Kunci jawapan

  1. 1. C · Ω (Big Omega)
  2. 2. D · O(n²)
  3. 3. C · O(n²)
  4. 4. C · O(V × E)
  5. 5. B · O(n)
  6. 6. C · Pilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
  7. 7. D · Θ(n log² n)
  8. 8. D · Θ(n log n)

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