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 tiga langkah algoritma bahagi dan takluk?

  1. ABaca, kira, tulis
  2. BBahagi, takluk, gabung
  3. CTeka, semak, ulang
  4. DIsih, cari, kembali
2.Mudah

Masa larian manakah yang polinomial?

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

Apakah kerumitan masa carian pertama dalam pada graf yang disimpan sebagai senarai bersebelahan?

  1. AO(V²)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V + E)
4.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)
5.Sederhana

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

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

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

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

Laluan ringkas terpendek boleh dicari dalam masa polinomial. Apakah yang diketahui tentang mencari laluan ringkas terpanjang antara dua bucu dalam graf am?

  1. AIa boleh diselesaikan oleh algoritma Dijkstra dengan pemberat dinegatifkan
  2. BIa tidak boleh diputuskan
  3. CIa sentiasa boleh diselesaikan dalam O(V + E)
  4. DIa NP-sukar
8.Sukar

Teknik manakah yang memberikan masa larian dijangka O(n log n) bagi isihan pantas pada sebarang input?

  1. AMemilih pangsi secara seragam rawak
  2. BMengisih input sebelum menjalankan isihan pantas
  3. CSentiasa memilih elemen pertama
  4. DMenggunakan rekursi pada sebelah kiri sahaja

Kunci jawapan

  1. 1. B · Bahagi, takluk, gabung
  2. 2. D · O(n³)
  3. 3. D · O(V + E)
  4. 4. B · O(n²)
  5. 5. A · O(n log n)
  6. 6. D · O(n)
  7. 7. D · Ia NP-sukar
  8. 8. A · Memilih pangsi secara seragam rawak

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