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 O(n²) mengambil 1 saat untuk n = 1000. Kira-kira berapa lamakah ia mengambil masa untuk n = 2000?

  1. A8 saat
  2. B4 saat
  3. C1 saat
  4. D2 saat
2.Mudah

Apakah yang diterangkan oleh masa larian kes terburuk sesuatu algoritma?

  1. AMasa yang diambil pada input terkecil
  2. BMasa dijangka yang diambil pada input rawak bersaiz n
  3. CMasa maksimum yang diambil merentasi semua input bersaiz n
  4. DMasa yang diambil pada komputer yang perlahan
3.Mudah

Apakah yang diterangkan oleh masa larian kes purata?

  1. ANilai tengah antara masa larian kes terbaik dan kes terburuk
  2. BMasa dijangka merentasi taburan input tertentu bersaiz n
  3. CMasa pada komputer yang paling biasa
  4. DMasa untuk input dengan panjang purata
4.Sederhana

Hubungan jadi semula T(n) = 2T(n/2) + O(n) mempunyai penyelesaian:

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

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

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

Dalam tatasusunan tersusun, anda mencari dua elemen yang jumlahnya sama dengan sasaran dengan menggerakkan satu penunjuk dari setiap hujung ke dalam. Apakah kerumitan masanya?

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

Bagaimanakah n! dan 2ⁿ dibandingkan untuk n yang besar?

  1. An! ialah O(n²)
  2. BKeduanya tumbuh pada kadar yang sama
  3. Cn! tumbuh lebih pantas daripada 2ⁿ
  4. D2ⁿ tumbuh lebih pantas daripada n!
8.Sukar

Algoritma manakah yang mencari pokok rentang minimum dengan menambah sisi termurah berulang kali yang tidak membentuk kitaran?

  1. AFloyd–Warshall
  2. BAlgoritma Dijkstra
  3. CAlgoritma Prim bermula dari satu nod
  4. DAlgoritma Kruskal

Kunci jawapan

  1. 1. B · 4 saat
  2. 2. C · Masa maksimum yang diambil merentasi semua input bersaiz n
  3. 3. B · Masa dijangka merentasi taburan input tertentu bersaiz n
  4. 4. B · O(n log n)
  5. 5. D · O(V × E)
  6. 6. A · O(n)
  7. 7. C · n! tumbuh lebih pantas daripada 2ⁿ
  8. 8. D · Algoritma Kruskal

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