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

Satu gelung bermula dengan i = 1 dan menggandakan i pada setiap lelaran sehingga i > n. Berapa banyak lelaran yang dijalankannya?

  1. AKira-kira n²
  2. BKira-kira log₂ n
  3. CKira-kira n / 2
  4. DKira-kira n
2.Mudah

Mengakses elemen mengikut indeks dalam tatasusunan mengambil masa:

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

Apakah maksudnya jika sesuatu operasi berjalan dalam masa O(1)?

  1. AMasa larinya tidak bertambah dengan saiz input
  2. BIa sentiasa mengambil tepat satu saat
  3. CIa memproses tepat satu elemen bagi setiap saat masa larian
  4. DIa hanya boleh dijalankan sekali
4.Sederhana

Dengan syiling 1, 3 dan 4 dan jumlah 6, berapa banyak syiling yang digunakan oleh kaedah tamak "syiling terbesar dahulu", berbanding optimum?

  1. ATamak menggunakan 3 syiling; optimum ialah 2
  2. BTamak menggunakan 2 syiling; optimum ialah 2
  3. CTamak menggunakan 4 syiling; optimum ialah 3
  4. DTamak menggunakan 3 syiling; optimum ialah 3
5.Sederhana

Mengapakah asas logaritma biasanya ditinggalkan dalam Big O, seperti dalam O(log n)?

  1. ASemua logaritma dalam sains komputer berasas 10, jadi ia tersirat
  2. BAsas hanya penting untuk n yang kecil
  3. CLogaritma dengan asas berbeza hanya berbeza oleh faktor malar
  4. DLogaritma sentiasa dibundarkan kepada integer
6.Sederhana

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

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

Bagaimanakah masalah jurujual kembara dikelaskan?

  1. AIa dalam P kerana algoritma Dijkstra menyelesaikannya dengan melawat setiap bandar sekali
  2. BVersi keputusan ialah NP-lengkap dan versi pengoptimuman ialah NP-sukar
  3. CVersi keputusan dalam P tetapi versi pengoptimuman NP-lengkap
  4. DIa tidak boleh diputuskan
8.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. CQuickselect berjalan dalam O(log n) kes terburuk, kerana ia berekursi pada satu sebelah pangsi sahaja
  4. DPemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan

Kunci jawapan

  1. 1. B · Kira-kira log₂ n
  2. 2. D · O(1)
  3. 3. A · Masa larinya tidak bertambah dengan saiz input
  4. 4. A · Tamak menggunakan 3 syiling; optimum ialah 2
  5. 5. C · Logaritma dengan asas berbeza hanya berbeza oleh faktor malar
  6. 6. A · O(log n)
  7. 7. B · Versi keputusan ialah NP-lengkap dan versi pengoptimuman ialah NP-sukar
  8. 8. A · Quickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk

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