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 dengan dua gelung bersarang, masing-masing berjalan n kali, biasanya mempunyai kerumitan yang mana?

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

Kerumitan ruang mengukur:

  1. ARuang cakera fail program setelah ia dikompil
  2. BSaiz fizikal komputer
  3. CJumlah memori yang diperlukan algoritma apabila input bertambah
  4. DBilangan baris kod
3.Mudah

Apakah kes asas bagi fungsi rekursif?

  1. APanggilan yang menggunakan paling banyak memori
  2. BKes yang dijawab terus tanpa membuat panggilan rekursif lain
  3. CKes dengan input terbesar, yang dikendalikan sebelum sebarang panggilan rekursif
  4. DBaris pertama fungsi
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 4 syiling; optimum ialah 3
  3. CTamak menggunakan 2 syiling; optimum ialah 2
  4. DTamak menggunakan 3 syiling; optimum ialah 3
5.Sederhana

Bagaimanakah algoritma Prim membina pokok rentang minimum?

  1. AIa menjalankan carian pertama lebar dan mengekalkan pokok BFS
  2. BIa mengisih semua sisi mengikut pemberat dan menambah setiap satu kecuali jika ia membentuk kitaran dalam hutan
  3. CIa membuang sisi paling mahal sehingga tiada kitaran tinggal
  4. DIa menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
6.Sederhana

Apakah masa larian isihan radiks LSD pada n integer dengan d digit dalam asas k?

  1. AO(n log n)
  2. BO(d(n + k))
  3. CO(dn log k)
  4. DO(n²)
7.Sukar

Masalah kebolehpuasan manakah yang diketahui boleh diselesaikan dalam masa polinomial?

  1. ASAT am pada formula dalam bentuk normal konjungtif
  2. BKebolehpuasan litar
  3. C2-SAT, yang setiap klausanya mempunyai paling banyak dua literal
  4. D3-SAT, yang setiap klausanya mempunyai tepat tiga literal
8.Sukar

Masalah galas 0/1 yang diselesaikan dengan pengaturcaraan dinamik mengambil masa O(nW). Mengapakah ini dipanggil pseudo-polinomial?

  1. AKerana n sentiasa kecil
  2. BW ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
  3. CKerana algoritma itu dirawakkan dan masa larinya berbeza-beza bagi setiap input
  4. DKerana ia hanya berfungsi untuk W = 0

Kunci jawapan

  1. 1. C · O(n²)
  2. 2. C · Jumlah memori yang diperlukan algoritma apabila input bertambah
  3. 3. B · Kes yang dijawab terus tanpa membuat panggilan rekursif lain
  4. 4. A · Tamak menggunakan 3 syiling; optimum ialah 2
  5. 5. D · Ia menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  6. 6. B · O(d(n + k))
  7. 7. C · 2-SAT, yang setiap klausanya mempunyai paling banyak dua literal
  8. 8. B · W ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W

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