Užduočių lapas tema Algoritmai ir sudėtingumas su atsakymais

Nemokamas spausdinamas užduočių lapas tema Algoritmai ir sudėtingumas: 8 uždavinių nuo lengvų iki egzamino lygio, su atsakymais. Atsispausdinkite arba išsaugokite kaip PDF.

Naujas užduočių lapasPraktikuokitės internete su užuominomis

Mokytojams: galima nemokamai spausdinti, kopijuoti ir naudoti per pamokas. Kiekvienas naujas lapas turi naujas reikšmes ir savo atsakymų raktą. Būsime dėkingi už nuorodą į ExamProblems jūsų kurso puslapyje.

Vardas: ____________________   Data: ____________

1.Lengvas

Ciklas pradeda nuo i = 1 ir kiekvienoje iteracijoje padvigubina i, kol i > n. Kiek iteracijų jis atlieka?

  1. AApie n²
  2. BApie n / 2
  3. CApie log₂ n
  4. DApie n
2.Lengvas

Kurią projektavimo strategiją naudoja rikiavimas suliejimu?

  1. AGodųjį pasirinkimą
  2. BSkaldyk ir valdyk
  3. CPerrinkimą (brute force)
  4. DDinaminį programavimą
3.Lengvas

O(n) algoritmas, kai n = 1 milijonas, trunka 3 sekundes. Maždaug kiek jis truks, kai n = 2 milijonai?

  1. A9 sekundes
  2. B3 sekundes
  3. C12 sekundžių
  4. D6 sekundes
4.Vidutinis

Paieška platyn nesvoriniame grafe randa:

  1. AMinimalų jungiamąjį medį
  2. BTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
  3. CTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  4. DTopologinę tvarką bet kuriame grafe
5.Vidutinis

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Koks yra dviejų n × n matricų daugybos standartiniu trigubu ciklu laiko sudėtingumas?

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

Heldo–Karpo dinaminio programavimo algoritmas tiksliai išsprendžia keliaujančio pirklio uždavinį. Koks jo vykdymo laikas n miestų?

  1. AO(n!)
  2. BO(n³)
  3. CO(n² 2ⁿ)
  4. DO(2n²)
8.Sunkus

Kokios yra n-tojo Fibonačio skaičiaus skaičiavimo ciklu, saugančiu tik dvi paskutines reikšmes, laiko ir atminties sąnaudos?

  1. AO(2ⁿ) laiko ir O(1) atminties
  2. BO(log n) laiko ir O(n) atminties
  3. CO(n) laiko ir O(1) atminties
  4. DO(n) laiko ir O(n) atminties

Atsakymai

  1. 1. C · Apie log₂ n
  2. 2. B · Skaldyk ir valdyk
  3. 3. D · 6 sekundes
  4. 4. C · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  5. 5. C · O(n log n)
  6. 6. A · O(n³)
  7. 7. C · O(n² 2ⁿ)
  8. 8. C · O(n) laiko ir O(1) atminties

Išsamūs sprendimai žingsnis po žingsnio: praktikuokite šią temą svetainėje examproblems.com.