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

Kam lygus log₂ 1024?

  1. A32
  2. B512
  3. C12
  4. D10
2.Lengvas

Kas yra rekursija?

  1. ARikiavimo metodas
  2. BCiklas, kuris niekada nesibaigia
  3. CDuomenų struktūros tipas
  4. DFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
3.Lengvas

Prieiga prie masyvo elemento pagal indeksą užtrunka:

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(n²)
4.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 2 monetas; optimalus sprendinys – 2
  3. CGodusis panaudoja 4 monetas; optimalus sprendinys – 3
  4. DGodusis panaudoja 3 monetas; optimalus sprendinys – 2
5.Vidutinis

Ar teisinga sakyti, kad O(n²) algoritmas yra ir O(n³)?

  1. ANe, nes dideliems n n³ mažesnis už n²
  2. BTaip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  3. CTaip, bet tik jei n mažesnis už 100
  4. DNe, nes didysis O visada turi nurodyti tikslų funkcijos augimo greitį
6.Vidutinis

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

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

Kaip dideliems n palyginami n! ir 2ⁿ?

  1. AJie auga vienodu greičiu
  2. Bn! yra O(n²)
  3. C2ⁿ auga greičiau už n!
  4. Dn! auga greičiau už 2ⁿ
8.Sunkus

Kodėl Dijkstros algoritmas gali duoti neteisingus rezultatus, kai kai kurie briaunų svoriai neigiami?

  1. ANeigiamų skaičių negalima saugoti prioritetinėje eilėje
  2. BTies kiekviena neigiama briauna jis patenka į begalinį ciklą
  3. CJis veikia tik su nekryptiniais grafais
  4. DViršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią

Atsakymai

  1. 1. D · 10
  2. 2. D · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  3. 3. C · O(1)
  4. 4. D · Godusis panaudoja 3 monetas; optimalus sprendinys – 2
  5. 5. B · Taip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  6. 6. A · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  7. 7. D · n! auga greičiau už 2ⁿ
  8. 8. D · Viršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią

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