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(log n)
  3. CO(n log n)
  4. DO(n)
2.Mudah

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

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

Algoritma isihan manakah yang memilih pangsi dan memetakan tatasusunan kepada elemen yang lebih kecil dan lebih besar?

  1. AIsihan sisipan
  2. BIsihan pantas
  3. CIsihan cantum
  4. DIsihan gelembung
4.Sederhana

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

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

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

  1. AMasalah itu boleh diselesaikan dalam masa malar
  2. BSetiap submasalah mempunyai saiz yang sama
  3. CPenyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya
  4. DMasalah itu mempunyai tepat satu penyelesaian optimum, yang dikongsi oleh setiap submasalah
6.Sederhana

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

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

Pernyataan manakah tentang P dan NP yang betul?

  1. ATelah dibuktikan bahawa P ≠ NP
  2. BMasalah NP tidak boleh disahkan dengan pantas
  3. CSetiap masalah dalam P juga dalam NP
  4. DNP bermaksud "bukan polinomial"
8.Sukar

Apakah kerumitan masa bagi: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lakukan kerja O(1)?

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

Kunci jawapan

  1. 1. B · O(log n)
  2. 2. B · O(n²)
  3. 3. B · Isihan pantas
  4. 4. C · O(2ⁿ)
  5. 5. C · Penyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya
  6. 6. B · O(log n)
  7. 7. C · Setiap masalah dalam P juga dalam NP
  8. 8. B · O(n log n)

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