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 terburuk isihan sisipan?

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

Apakah rekursi?

  1. AKaedah isihan
  2. BGelung yang tidak pernah berakhir
  3. CSejenis struktur data
  4. DFungsi yang memanggil dirinya sendiri pada input yang lebih kecil
3.Mudah

Yang manakah tumbuh paling perlahan apabila n menjadi besar?

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

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(d(n + k))
  4. DO(dn log k)
5.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 2 syiling; optimum ialah 2
  3. CTamak menggunakan 4 syiling; optimum ialah 3
  4. DTamak menggunakan 3 syiling; optimum ialah 3
6.Sederhana

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

  1. AO(n log n)
  2. BO(n³)
  3. CO(n)
  4. DO(n²)
7.Sukar

Mengapakah algoritma Dijkstra boleh memberikan keputusan yang salah apabila sesetengah pemberat sisi negatif?

  1. ASesuatu bucu dimuktamadkan apabila dikeluarkan, tetapi sisi negatif kemudian masih boleh memberinya laluan yang lebih pendek
  2. BNombor negatif tidak boleh disimpan dalam baris gilir keutamaan
  3. CIa masuk ke dalam gelung tak terhingga pada setiap sisi negatif
  4. DIa hanya berfungsi pada graf tidak berarah
8.Sukar

Pendaraban Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apakah penyelesaiannya?

  1. AΘ(nlog₂ 3), kira-kira n1.585
  2. BΘ(n log n)
  3. CΘ(n3)
  4. DΘ(n²)

Kunci jawapan

  1. 1. C · O(n²)
  2. 2. D · Fungsi yang memanggil dirinya sendiri pada input yang lebih kecil
  3. 3. D · O(log n)
  4. 4. C · O(d(n + k))
  5. 5. A · Tamak menggunakan 3 syiling; optimum ialah 2
  6. 6. D · O(n²)
  7. 7. A · Sesuatu bucu dimuktamadkan apabila dikeluarkan, tetapi sisi negatif kemudian masih boleh memberinya laluan yang lebih pendek
  8. 8. A · Θ(nlog₂ 3), kira-kira n1.585

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