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 masa larian isihan kiraan bagi n integer dalam julat 0 hingga k?

  1. AO(n²)
  2. BO(k log n)
  3. CO(n + k)
  4. DO(n log n)
2.Mudah

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

  1. AO(V²)
  2. BO(V × E)
  3. CO(E log V)
  4. DO(V + E)
3.Mudah

Apakah rekursi?

  1. ASejenis struktur data
  2. BKaedah isihan
  3. CGelung yang tidak pernah berakhir
  4. DFungsi yang memanggil dirinya sendiri pada input yang lebih kecil
4.Sederhana

Apakah kerumitan masa bagi: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Apakah kerumitan masa teramortisasi bagi menambah pada tatasusunan dinamik yang menggandakan kapasitinya apabila penuh?

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

Dengan syiling 1, 3 dan 4 dan jumlah 6, berapa banyak syiling yang digunakan oleh kaedah tamak "syiling terbesar dahulu", berbanding optimum?

  1. ATamak menggunakan 3 syiling; optimum ialah 2
  2. BTamak menggunakan 3 syiling; optimum ialah 3
  3. CTamak menggunakan 2 syiling; optimum ialah 2
  4. DTamak menggunakan 4 syiling; optimum ialah 3
7.Sukar

Apakah masa larian algoritma Dijkstra dengan timbunan binari pada graf dengan V bucu dan E sisi?

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

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

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

Kunci jawapan

  1. 1. C · O(n + k)
  2. 2. D · O(V + E)
  3. 3. D · Fungsi yang memanggil dirinya sendiri pada input yang lebih kecil
  4. 4. A · O(n²)
  5. 5. B · O(1)
  6. 6. A · Tamak menggunakan 3 syiling; optimum ialah 2
  7. 7. D · O((V + E) log V)
  8. 8. A · Pokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n

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