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

Masa larian manakah yang polinomial?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
2.Mudah

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

  1. AIa tidak mempunyai penyelesaian
  2. BIa boleh diselesaikan dalam masa malar
  3. CIa hanya boleh diselesaikan dengan mencuba setiap kemungkinan
  4. DIa boleh diselesaikan dalam masa polinomial
3.Mudah

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

  1. AO(n²)
  2. BO(2ⁿ)
  3. CO(n log n)
  4. DO(n³)
4.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)
  2. BO(n²)
  3. CO(n log n)
  4. DO(log n)
5.Sederhana

Pengaturcaraan dinamik berguna apabila sesuatu masalah mempunyai:

  1. ASatu gelung
  2. BHanya input rawak
  3. CTiada submasalah langsung, jadi ia boleh diselesaikan dalam satu langkah
  4. DSubmasalah bertindih dan substruktur optimum
6.Sederhana

Algoritma tamak (greedy):

  1. AMencuba setiap penyelesaian yang mungkin
  2. BHanya menggunakan rekursi
  3. CMembuat pilihan terbaik setempat pada setiap langkah
  4. DSentiasa memberikan penyelesaian optimum
7.Sukar

Apakah kerumitan masa bagi: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lakukan kerja O(1)?

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

Apakah kos teramortisasi menokok pembilang binari, memandangkan satu tokokan boleh membalikkan banyak bit?

  1. AO(log n) bagi setiap tokokan
  2. BO(n) bagi setiap tokokan
  3. CO(1) bagi setiap tokokan
  4. DO(n log n) bagi setiap tokokan

Kunci jawapan

  1. 1. C · O(n³)
  2. 2. D · Ia boleh diselesaikan dalam masa polinomial
  3. 3. B · O(2ⁿ)
  4. 4. A · O(n)
  5. 5. D · Submasalah bertindih dan substruktur optimum
  6. 6. C · Membuat pilihan terbaik setempat pada setiap langkah
  7. 7. B · O(n log n)
  8. 8. C · O(1) bagi setiap tokokan

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