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 yang diterangkan oleh masa larian kes terburuk sesuatu algoritma?

  1. AMasa maksimum yang diambil merentasi semua input bersaiz n
  2. BMasa dijangka yang diambil pada input rawak bersaiz n
  3. CMasa yang diambil pada input terkecil
  4. DMasa yang diambil pada komputer yang perlahan
2.Mudah

Apakah rekursi?

  1. AGelung yang tidak pernah berakhir
  2. BFungsi yang memanggil dirinya sendiri pada input yang lebih kecil
  3. CSejenis struktur data
  4. DKaedah isihan
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 log₂ n
  2. BKira-kira n
  3. CKira-kira n / 2
  4. DKira-kira n²
4.Sederhana

Apakah yang diukur oleh analisis teramortisasi?

  1. AKos satu operasi yang paling mahal di mana-mana dalam jujukan itu
  2. BKos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  3. CKos algoritma pada input terbaik
  4. DKos dijangka merentasi input rawak
5.Sederhana

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

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V³ × E)
  4. DO(V × E)
6.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
7.Sukar

Apakah yang dibuktikan oleh teorem Cook–Levin?

  1. ASetiap masalah NP boleh diselesaikan dalam masa eksponen
  2. BP tidak sama dengan NP
  3. CMasalah kebolehpuasan Boolean (SAT) ialah NP-lengkap
  4. DMasalah penghentian tidak boleh diputuskan
8.Sukar

Dua perkara manakah yang mesti ditunjukkan untuk membuktikan bahawa masalah keputusan X ialah NP-lengkap?

  1. AX dalam P, dan X boleh diturunkan kepada SAT
  2. BX boleh diturunkan kepada masalah dalam P, dan X dalam NP
  3. CX tiada algoritma polinomial, dan X boleh diputuskan
  4. DX dalam NP, dan masalah NP-lengkap yang diketahui boleh diturunkan kepada X dalam masa polinomial

Kunci jawapan

  1. 1. A · Masa maksimum yang diambil merentasi semua input bersaiz n
  2. 2. B · Fungsi yang memanggil dirinya sendiri pada input yang lebih kecil
  3. 3. A · Kira-kira log₂ n
  4. 4. B · Kos purata bagi setiap operasi merentasi jujukan operasi kes terburuk
  5. 5. D · O(V × E)
  6. 6. C · Ia menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  7. 7. C · Masalah kebolehpuasan Boolean (SAT) ialah NP-lengkap
  8. 8. D · X dalam NP, dan masalah NP-lengkap yang diketahui boleh diturunkan kepada X dalam masa polinomial

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