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

Kelas kerumitan manakah yang tumbuh paling pantas untuk n yang besar?

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

Apakah memoisasi?

  1. AMenukar rekursi menjadi gelung setara secara automatik supaya tiada tindanan panggilan diperlukan
  2. BMenyimpan hasil panggilan fungsi supaya panggilan berulang dijawab daripada memori
  3. CMembebaskan memori selepas fungsi kembali
  4. DMenulis komen di sebelah setiap baris kod
3.Mudah

Algoritma O(n²) mengambil 1 saat untuk n = 1000. Kira-kira berapa lamakah ia mengambil masa untuk n = 2000?

  1. A8 saat
  2. B2 saat
  3. C1 saat
  4. D4 saat
4.Sederhana

Kerumitan masa Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) ialah:

  1. AEksponen
  2. BLinear
  3. CLogaritma
  4. DMalar
5.Sederhana

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

  1. AO(E log V)
  2. BO(V³ × E)
  3. CO(V × E)
  4. DO(V + E)
6.Sederhana

Kira-kira berapa banyak perbandingan yang diperlukan oleh carian binari dalam kes terburuk pada tatasusunan tersusun 1,000,000 elemen?

  1. AKira-kira 500,000
  2. BKira-kira 100
  3. CKira-kira 20
  4. DKira-kira 1,000
7.Sukar

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

  1. AMasa O(log n) dan ruang O(n)
  2. BMasa O(n) dan ruang O(n)
  3. CMasa O(n) dan ruang O(1)
  4. DMasa O(2ⁿ) dan ruang O(1)
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, kerana isihan sisipan bukan isihan perbandingan
  2. BYa, oleh itu batas bawah itu salah
  3. CYa, tetapi hanya untuk tatasusunan lebih pendek daripada 100
  4. DTidak, batas bawah terpakai pada kes terburuk merentasi semua input, bukan pada setiap input

Kunci jawapan

  1. 1. D · O(2ⁿ)
  2. 2. B · Menyimpan hasil panggilan fungsi supaya panggilan berulang dijawab daripada memori
  3. 3. D · 4 saat
  4. 4. A · Eksponen
  5. 5. C · O(V × E)
  6. 6. C · Kira-kira 20
  7. 7. C · Masa O(n) dan ruang O(1)
  8. 8. D · 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.