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. B2 saat
  3. C8 saat
  4. D1 saat
2.Mudah

Apakah algoritma?

  1. AMana-mana program komputer yang mempunyai antara muka grafik
  2. BStruktur data yang menyimpan nombor
  3. CBahasa pengaturcaraan yang direka untuk menulis formula matematik
  4. DJujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
3.Mudah

Kelas kerumitan manakah yang tumbuh paling pantas untuk n yang besar?

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

Apakah kerumitan masa kes terburuk isihan pantas?

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

Dalam tatasusunan tersusun, anda mencari dua elemen yang jumlahnya sama dengan sasaran dengan menggerakkan satu penunjuk dari setiap hujung ke dalam. Apakah kerumitan masanya?

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

Algoritma manakah yang mencari laluan terpendek dari satu sumber dalam graf dengan pemberat sisi tidak negatif?

  1. AAlgoritma Kruskal
  2. BCarian pertama dalam
  3. CAlgoritma Dijkstra
  4. DBellman–Ford diperlukan dalam semua kes
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(2ⁿ) dan ruang O(1)
  3. CMasa O(n) dan ruang O(n)
  4. DMasa O(n) dan ruang O(1)
8.Sukar

Mengapakah carian binari tidak memberikan masa O(log n) pada senarai berpaut tunggal?

  1. ASenarai berpaut tidak boleh disusun
  2. BSampai ke elemen tengah mengambil O(n) langkah, kerana tiada akses indeks langsung
  3. CPerbandingan pada nod senarai berpaut lebih perlahan
  4. DCarian binari memerlukan memori dua kali ganda

Kunci jawapan

  1. 1. A · 4 saat
  2. 2. D · Jujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
  3. 3. A · O(2ⁿ)
  4. 4. A · O(n²)
  5. 5. C · O(n)
  6. 6. C · Algoritma Dijkstra
  7. 7. D · Masa O(n) dan ruang O(1)
  8. 8. B · Sampai ke elemen tengah mengambil O(n) langkah, kerana tiada akses indeks langsung

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