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

Berapa banyak memori tambahan yang digunakan oleh isihan cantum berasaskan tatasusunan piawai?

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

Apakah tiga langkah algoritma bahagi dan takluk?

  1. ATeka, semak, ulang
  2. BBahagi, takluk, gabung
  3. CBaca, kira, tulis
  4. DIsih, cari, kembali
3.Mudah

Apakah kerumitan masa mencari nilai terbesar dalam tatasusunan tidak tersusun yang mengandungi n nombor?

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

Apakah masa larian isihan radiks LSD pada n integer dengan d digit dalam asas k?

  1. AO(n log n)
  2. BO(d(n + k))
  3. CO(dn log k)
  4. DO(n²)
5.Sederhana

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

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

Batas bawah bagi isihan berasaskan perbandingan dalam kes terburuk ialah:

  1. AΩ(n log n)
  2. BΩ(n)
  3. CΩ(n²)
  4. DΩ(log n)
7.Sukar

Menggunakan teorem induk, T(n) = 8T(n/2) + O(n²) mempunyai penyelesaian:

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

Isihan topologi hanya mungkin untuk:

  1. AGraf tidak berarah
  2. BGraf dengan pemberat negatif
  3. CGraf berarah tanpa kitaran
  4. DGraf lengkap

Kunci jawapan

  1. 1. C · O(n)
  2. 2. B · Bahagi, takluk, gabung
  3. 3. C · O(n)
  4. 4. B · O(d(n + k))
  5. 5. C · O(2ⁿ)
  6. 6. A · Ω(n log n)
  7. 7. A · Θ(n³)
  8. 8. C · Graf berarah tanpa kitaran

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