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 kerumitan masa kes terbaik isihan sisipan, pada tatasusunan yang sudah tersusun?

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

Masa larian manakah yang polinomial?

  1. AO(n!)
  2. BO(2ⁿ)
  3. CO(nⁿ)
  4. DO(n³)
3.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 n
  3. CKira-kira log₂ n
  4. DKira-kira n / 2
4.Sederhana

Hubungan jadi semula T(n) = 2T(n/2) + O(n) mempunyai penyelesaian:

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

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

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

Algoritma isihan manakah yang stabil?

  1. AIsihan pantas (versi dalam-tempat biasa)
  2. BIsihan pemilihan (versi biasa)
  3. CIsihan timbunan
  4. DIsihan cantum
7.Sukar

Laluan ringkas terpendek boleh dicari dalam masa polinomial. Apakah yang diketahui tentang mencari laluan ringkas terpanjang antara dua bucu dalam graf am?

  1. AIa boleh diselesaikan oleh algoritma Dijkstra dengan pemberat dinegatifkan
  2. BIa tidak boleh diputuskan
  3. CIa NP-sukar
  4. DIa sentiasa boleh diselesaikan dalam O(V + E)
8.Sukar

Algoritma pengaturcaraan dinamik Held–Karp menyelesaikan masalah jurujual kembara dengan tepat. Apakah masa larinya untuk n bandar?

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

Kunci jawapan

  1. 1. B · O(n)
  2. 2. D · O(n³)
  3. 3. C · Kira-kira log₂ n
  4. 4. C · O(n log n)
  5. 5. C · O(n²)
  6. 6. D · Isihan cantum
  7. 7. C · Ia NP-sukar
  8. 8. D · O(n² 2ⁿ)

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