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 berulang kali menukar elemen bersebelahan yang berada dalam susunan yang salah?

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

Apakah kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

  1. AO(n²)
  2. BO(1)
  3. CO(n)
  4. DO(log 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
  2. BKira-kira log₂ n
  3. CKira-kira n
  4. DKira-kira n²
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 3
  2. BTamak menggunakan 3 syiling; optimum ialah 2
  3. CTamak menggunakan 4 syiling; optimum ialah 3
  4. DTamak menggunakan 2 syiling; optimum ialah 2
5.Sederhana

Bagaimanakah algoritma Prim membina pokok rentang minimum?

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

Apakah penyelesaian hubungan jadi semula T(n) = T(n − 1) + O(n)?

  1. AO(n log n)
  2. BO(n)
  3. CO(n²)
  4. DO(2ⁿ)
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²)
  2. BO(n log n)
  3. CO(n √n)
  4. DO(n)
8.Sukar

Isihan sisipan berjalan dalam O(n) pada input tersusun. Adakah ini bercanggah dengan batas bawah Ω(n log n) untuk isihan perbandingan?

  1. ATidak, batas bawah terpakai pada kes terburuk merentasi semua input, bukan pada setiap input
  2. BYa, oleh itu batas bawah itu salah
  3. CYa, tetapi hanya untuk tatasusunan lebih pendek daripada 100
  4. DTidak, kerana isihan sisipan bukan isihan perbandingan

Kunci jawapan

  1. 1. C · Isihan gelembung
  2. 2. C · O(n)
  3. 3. B · Kira-kira log₂ n
  4. 4. B · Tamak menggunakan 3 syiling; optimum ialah 2
  5. 5. C · Ia menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok
  6. 6. C · O(n²)
  7. 7. B · O(n log n)
  8. 8. A · Tidak, batas bawah terpakai pada kes terburuk merentasi semua input, bukan pada setiap input

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