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 isihan manakah yang memilih pangsi dan memetakan tatasusunan kepada elemen yang lebih kecil dan lebih besar?

  1. AIsihan sisipan
  2. BIsihan cantum
  3. CIsihan pantas
  4. DIsihan gelembung
2.Mudah

Apakah algoritma kekerasan (brute force)?

  1. AYang berjalan pada banyak pemproses
  2. BYang sentiasa menggunakan rekursi
  3. CYang mencuba semua calon penyelesaian yang mungkin
  4. DYang meneka jawapan secara rawak
3.Mudah

Notasi manakah yang menerangkan batas atas pertumbuhan?

  1. ABig O
  2. BOmega kecil
  3. CBig Omega
  4. DBig Theta
4.Sederhana

Apakah kerumitan masa algoritma Bellman–Ford pada graf dengan V bucu dan E sisi?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V³ × E)
5.Sederhana

Bagaimanakah algoritma Prim membina pokok rentang minimum?

  1. AIa menjalankan carian pertama lebar dan mengekalkan pokok BFS
  2. BIa membuang sisi paling mahal sehingga tiada kitaran tinggal
  3. CIa menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  4. DIa mengisih semua sisi mengikut pemberat dan menambah setiap satu kecuali jika ia membentuk kitaran dalam hutan
6.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 log n)
  3. CO(log n)
  4. DO(n)
7.Sukar

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

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(n log² n)
  4. DΘ(n)
8.Sukar

Apakah perbezaan antara masalah yang tidak boleh diputuskan dengan masalah yang tidak boleh dikendalikan (intractable)?

  1. AMasalah tak boleh diputuskan tiada algoritma untuk semua input; masalah tak boleh dikendalikan ada algoritma, tetapi terlalu perlahan
  2. BKedua-duanya bermaksud masalah itu tidak mempunyai algoritma sama sekali
  3. CMasalah tak boleh dikendalikan tidak dapat diselesaikan oleh sebarang algoritma, manakala yang tak boleh diputuskan hanya memerlukan masa eksponen
  4. DMasalah tak boleh diputuskan berada dalam NP, manakala masalah tak boleh dikendalikan berada dalam P

Kunci jawapan

  1. 1. C · Isihan pantas
  2. 2. C · Yang mencuba semua calon penyelesaian yang mungkin
  3. 3. A · Big O
  4. 4. A · O(V × E)
  5. 5. C · Ia menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  6. 6. D · O(n)
  7. 7. C · Θ(n log² n)
  8. 8. A · Masalah tak boleh diputuskan tiada algoritma untuk semua input; masalah tak boleh dikendalikan ada algoritma, tetapi terlalu perlahan

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