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

Algoritma isihan manakah yang memilih pangsi dan memetakan tatasusunan kepada elemen yang lebih kecil dan lebih besar?

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

Apakah pertumbuhan O(2ⁿ) dipanggil?

  1. ALogaritma
  2. BEksponen
  3. CPolinomial
  4. DLinear
4.Sederhana

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

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

Anda mengisih tatasusunan n elemen sekali dan kemudian menjawab k pertanyaan keahlian dengan carian binari. Apakah jumlah kosnya?

  1. AO(nk)
  2. BO(k n log n)
  3. CO(n log n + k log n)
  4. DO(n + k)
6.Sederhana

Apakah kerumitan masa bagi: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Apakah kos masa dan ruang mengira nombor Fibonacci ke-n dengan gelung yang hanya menyimpan dua nilai terakhir?

  1. AMasa O(n) dan ruang O(1)
  2. BMasa O(2ⁿ) dan ruang O(1)
  3. CMasa O(n) dan ruang O(n)
  4. DMasa O(log n) dan ruang O(n)
8.Sukar

Algoritma Strassen mendarab matriks menggunakan 7 dan bukannya 8 pendaraban rekursif blok separuh saiz. Apakah masa larinya?

  1. AΘ(nlog₂ 7), kira-kira n2.81
  2. BΘ(n2)
  3. CΘ(n² log n)
  4. DΘ(n³)

Kunci jawapan

  1. 1. C · Isihan gelembung
  2. 2. D · Isihan pantas
  3. 3. B · Eksponen
  4. 4. D · O(log n)
  5. 5. C · O(n log n + k log n)
  6. 6. C · O(n log n)
  7. 7. A · Masa O(n) dan ruang O(1)
  8. 8. A · Θ(nlog₂ 7), kira-kira n2.81

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