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

Kaip vadinamas O(2ⁿ) augimas?

  1. AEksponentinis
  2. BPolinominis
  3. CTiesinis
  4. DLogaritminis
2.Lengvas

Kas yra memoizacija?

  1. AKomentarų rašymas prie kiekvienos kodo eilutės
  2. BAtminties atlaisvinimas funkcijai grįžus
  3. CFunkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
  4. DAutomatinis rekursijos pavertimas ekvivalenčiu ciklu, kad nebereikėtų kvietimų steko
3.Lengvas

Algoritmo vykdymo laikas yra O(n). Kaip vadinamas toks augimas?

  1. ATiesinis
  2. BKvadratinis
  3. CLogaritminis
  4. DPastovus
4.Vidutinis

Ką apskaičiuoja Floydo–Warshallo algoritmas ir kaip greitai?

  1. ATopologinę tvarką per O(V²)
  2. BTrumpiausius kelius tarp visų viršūnių porų per O(V³)
  3. CMinimalų jungiamąjį medį per O(E log V)
  4. DTrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)
5.Vidutinis

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for j = 1 to i: atlikti O(1) darbą?

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

Turint 1, 3 ir 4 vertės monetas ir 6 sumą, kiek monetų panaudoja godusis metodas „pirmiausia didžiausia moneta“, palyginti su optimaliu sprendiniu?

  1. AGodusis panaudoja 3 monetas; optimalus sprendinys – 3
  2. BGodusis panaudoja 3 monetas; optimalus sprendinys – 2
  3. CGodusis panaudoja 4 monetas; optimalus sprendinys – 3
  4. DGodusis panaudoja 2 monetas; optimalus sprendinys – 2
7.Sunkus

Kuriam kuprinės uždavinio variantui godžioji taisyklė „imti daiktus pagal vertės ir svorio santykį“ visada duoda optimalų atsakymą?

  1. AAbiem variantams
  2. BTrupmeninei kuprinei, kai daiktus galima dalyti
  3. C0/1 kuprinei, kai daiktai visada imami ištisi
  4. DNė vienam variantui
8.Sunkus

Kuris teiginys apie k-ojo mažiausio nesurikiuoto masyvo elemento išrinkimą teisingas?

  1. AIšrinkimui visada reikia Ω(n log n), nes reikia rikiavimo
  2. BIšrinkimas įmanomas tik per O(n²)
  3. CQuickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju
  4. DQuickselect blogiausiu atveju veikia per O(log n), nes rekursija vyksta tik į vieną atramos elemento pusę

Atsakymai

  1. 1. A · Eksponentinis
  2. 2. C · Funkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
  3. 3. A · Tiesinis
  4. 4. B · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  5. 5. D · O(n²)
  6. 6. B · Godusis panaudoja 3 monetas; optimalus sprendinys – 2
  7. 7. B · Trupmeninei kuprinei, kai daiktus galima dalyti
  8. 8. C · Quickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju

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