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

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

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

Apakah kerumitan masa carian binari pada tatasusunan yang telah disusun?

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

Notasi manakah yang menerangkan batas atas pertumbuhan?

  1. ABig Omega
  2. BBig O
  3. CBig Theta
  4. DOmega kecil
4.Sederhana

Apakah yang diukur oleh analisis teramortisasi?

  1. AKos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  2. BKos dijangka merentasi input rawak
  3. CKos satu operasi yang paling mahal di mana-mana dalam jujukan itu
  4. DKos algoritma pada input terbaik
5.Sederhana

Algoritma tamak (greedy):

  1. AHanya menggunakan rekursi
  2. BMembuat pilihan terbaik setempat pada setiap langkah
  3. CMencuba setiap penyelesaian yang mungkin
  4. DSentiasa memberikan penyelesaian optimum
6.Sederhana

Apakah kerumitan masa kes terburuk isihan pantas?

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

Apakah kos masa dan ruang mengira nombor Fibonacci ke-n dengan gelung yang hanya menyimpan dua nilai terakhir?

  1. AMasa O(log n) dan ruang O(n)
  2. BMasa O(n) dan ruang O(1)
  3. CMasa O(2ⁿ) dan ruang O(1)
  4. DMasa O(n) dan ruang O(n)
8.Sukar

Mengapakah carian purata dalam jadual cincang ialah O(1) tetapi kes terburuk O(n)?

  1. ABanyak kunci mungkin berlanggar ke dalam baldi yang sama
  2. BTatasusunan mempunyai akses O(n)
  3. CFungsi cincang adalah perlahan
  4. DKunci mesti disusun dahulu

Kunci jawapan

  1. 1. D · O(n²)
  2. 2. A · O(log n)
  3. 3. B · Big O
  4. 4. A · Kos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  5. 5. B · Membuat pilihan terbaik setempat pada setiap langkah
  6. 6. A · O(n²)
  7. 7. B · Masa O(n) dan ruang O(1)
  8. 8. A · Banyak kunci mungkin berlanggar ke dalam baldi yang sama

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