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

Koks yra 3n² + 5n + 2 didysis O?

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

Kam lygus log₂ 1024?

  1. A10
  2. B32
  3. C512
  4. D12
3.Lengvas

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

  1. AMažoji omega
  2. BDidžioji Teta
  3. CDidžioji Omega
  4. DDidysis O
4.Vidutinis

Kuris teiginys apie rekursinę funkciją be pasiekiamo bazinio atvejo teisingas?

  1. AJi vis kviečia save, kol perpildomas kvietimų stekas
  2. BJi veikia per O(1) laiką
  3. CKompiliatorius visada ją paverčia ciklu, kuris saugiai pasibaigia
  4. DJi automatiškai grąžina 0
5.Vidutinis

Kam lygus rekurentinės lygties T(n) = 2T(n − 1) + O(1) sprendinys?

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

Kam lygus rekurentinės lygties T(n) = T(n/2) + O(1) sprendinys?

  1. AO(n log n)
  2. BO(log n)
  3. CO(1)
  4. DO(n)
7.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. BViršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią
  3. CJis veikia tik su nekryptiniais grafais
  4. DTies kiekviena neigiama briauna jis patenka į begalinį ciklą
8.Sunkus

Kuris metodas užtikrina tikėtiną O(n log n) greitojo rikiavimo vykdymo laiką bet kokiems įvesties duomenims?

  1. ARekursijos taikymas tik kairiajai pusei
  2. BVisada pirmojo elemento parinkimas
  3. CĮvesties duomenų surikiavimas prieš paleidžiant greitąjį rikiavimą
  4. DAtraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį

Atsakymai

  1. 1. C · O(n²)
  2. 2. A · 10
  3. 3. D · Didysis O
  4. 4. A · Ji vis kviečia save, kol perpildomas kvietimų stekas
  5. 5. A · O(2ⁿ)
  6. 6. B · O(log n)
  7. 7. B · Viršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią
  8. 8. D · Atraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį

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