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 yang diperlukan oleh carian binari daripada inputnya?

  1. ATatasusunan mestilah tersusun
  2. BTatasusunan tidak boleh mempunyai lebih daripada 1000 elemen
  3. CTatasusunan mesti mengandungi nombor positif sahaja
  4. DPanjang tatasusunan mestilah kuasa dua
2.Mudah

Apakah memoisasi?

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

Yang manakah tumbuh paling perlahan apabila n menjadi besar?

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

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

  1. AO(n + k)
  2. BO(k n log n)
  3. CO(n log n + k log n)
  4. DO(nk)
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

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

  1. AEksponen
  2. BMalar
  3. CLinear
  4. DLogaritma
7.Sukar

Mengapakah sebarang carian berasaskan perbandingan dalam tatasusunan tersusun memerlukan Ω(log n) perbandingan dalam kes terburuk?

  1. ACarian binari ialah satu-satunya algoritma yang mungkin, dan ia memerlukan log₂ n perbandingan
  2. BPerbandingan mengambil masa logaritma setiap satu
  3. CSetiap elemen mesti dibandingkan sekurang-kurangnya sekali
  4. DPokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n
8.Sukar

Pernyataan manakah tentang P dan NP yang betul?

  1. ASetiap masalah dalam P juga dalam NP
  2. BTelah dibuktikan bahawa P ≠ NP
  3. CNP bermaksud "bukan polinomial"
  4. DMasalah NP tidak boleh disahkan dengan pantas

Kunci jawapan

  1. 1. A · Tatasusunan mestilah tersusun
  2. 2. B · Menyimpan hasil panggilan fungsi supaya panggilan berulang dijawab daripada memori
  3. 3. D · O(log n)
  4. 4. C · O(n log n + k log n)
  5. 5. D · O(V × E)
  6. 6. A · Eksponen
  7. 7. D · Pokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n
  8. 8. A · Setiap masalah dalam P juga dalam NP

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