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

Algoritma O(n²) mengambil 1 saat untuk n = 1000. Kira-kira berapa lamakah ia mengambil masa untuk n = 2000?

  1. A4 saat
  2. B8 saat
  3. C2 saat
  4. D1 saat
2.Mudah

Apakah kerumitan masa kes terburuk isihan sisipan?

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

Apakah log₂ 1024?

  1. A10
  2. B32
  3. C512
  4. D12
4.Sederhana

Pengaturcaraan dinamik berguna apabila sesuatu masalah mempunyai:

  1. ASatu gelung
  2. BHanya input rawak
  3. CSubmasalah bertindih dan substruktur optimum
  4. DTiada submasalah langsung, jadi ia boleh diselesaikan dalam satu langkah
5.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)
6.Sederhana

Bagaimanakah algoritma Prim membina pokok rentang minimum?

  1. AIa menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  2. BIa membuang sisi paling mahal sehingga tiada kitaran tinggal
  3. CIa menjalankan carian pertama lebar dan mengekalkan pokok BFS
  4. DIa mengisih semua sisi mengikut pemberat dan menambah setiap satu kecuali jika ia membentuk kitaran dalam hutan
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. CPemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan
  4. DQuickselect berjalan dalam O(log n) kes terburuk, kerana ia berekursi pada satu sebelah pangsi sahaja
8.Sukar

Algoritma Strassen mendarab matriks menggunakan 7 dan bukannya 8 pendaraban rekursif blok separuh saiz. Apakah masa larinya?

  1. AΘ(n2)
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(nlog₂ 7), kira-kira n2.81

Kunci jawapan

  1. 1. A · 4 saat
  2. 2. C · O(n²)
  3. 3. A · 10
  4. 4. C · Submasalah bertindih dan substruktur optimum
  5. 5. D · O(n)
  6. 6. A · Ia menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  7. 7. A · Quickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk
  8. 8. D · Θ(nlog₂ 7), kira-kira n2.81

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