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. ALogaritminis
  2. BTiesinis
  3. CEksponentinis
  4. DPolinominis
2.Lengvas

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

  1. A12 sekundžių
  2. B3 sekundes
  3. C9 sekundes
  4. D6 sekundes
3.Lengvas

Ko dvejetainė paieška reikalauja iš savo įvesties?

  1. AMasyvo ilgis turi būti dvejeto laipsnis
  2. BMasyvas turi būti surikiuotas
  3. CMasyve turi būti tik teigiami skaičiai
  4. DMasyve turi būti ne daugiau kaip 1000 elementų
4.Vidutinis

Palyginimais pagrįsto rikiavimo apatinis rėžis blogiausiu atveju yra:

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n²)
  4. DΩ(n)
5.Vidutinis

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu atsitiktinės tvarkos masyvu
  2. BSu jau surikiuotu masyvu
  3. CSu masyvu, kurio visi elementai skirtingi
  4. DSu 2 ilgio masyvu
6.Vidutinis

Koks yra Bellmano–Fordo algoritmo laiko sudėtingumas grafui su V viršūnių ir E briaunų?

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

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

  1. ATies kiekviena neigiama briauna jis patenka į begalinį ciklą
  2. BNeigiamų skaičių negalima saugoti prioritetinėje eilėje
  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ą
8.Sunkus

0/1 kuprinės uždavinys, sprendžiamas dinaminiu programavimu, užtrunka O(nW) laiko. Kodėl tai vadinama pseudopolinominiu laiku?

  1. ANes algoritmas yra atsitiktinis ir jo vykdymo laikas kinta su kiekviena įvestimi
  2. BW yra skaitinė reikšmė, todėl laikas yra eksponentinis bitų, reikalingų W užrašyti, skaičiaus atžvilgiu
  3. CNes jis veikia tik kai W = 0
  4. DNes n visada mažas

Atsakymai

  1. 1. C · Eksponentinis
  2. 2. D · 6 sekundes
  3. 3. B · Masyvas turi būti surikiuotas
  4. 4. A · Ω(n log n)
  5. 5. B · Su jau surikiuotu masyvu
  6. 6. A · O(V × E)
  7. 7. D · Viršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią
  8. 8. B · W yra skaitinė reikšmė, todėl laikas yra eksponentinis bitų, reikalingų W užrašyti, skaičiaus atžvilgiu

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