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

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

  1. ATiesinis
  2. BPastovus
  3. CLogaritminis
  4. DKvadratinis
2.Lengvas

Koks yra rikiavimo skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

  1. AO(k log n)
  2. BO(n + k)
  3. CO(n log n)
  4. DO(n²)
3.Lengvas

Ką reiškia f(n) = Θ(g(n))?

  1. Af auga griežtai greičiau už g
  2. Bf auga griežtai lėčiau už g
  3. Cf auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  4. Df visada mažesnė už g su kiekvienu n, todėl g riboja ją iš viršaus, bet niekada iš apačios
4.Vidutinis

Vieną kartą surikiuojate n elementų masyvą, o tada dvejetaine paieška atsakote į k priklausomybės užklausų. Kokia bendra kaina?

  1. AO(n log n + k log n)
  2. BO(nk)
  3. CO(n + k)
  4. DO(k n log n)
5.Vidutinis

Kiek lygmenų turi rikiavimo suliejimu rekursija n elementų masyvui?

  1. AApie √n
  2. BApie log₂ n
  3. CApie n
  4. DApie n / 2
6.Vidutinis

Koks yra n-tojo Fibonačio skaičiaus skaičiavimo laiko sudėtingumas, naudojant lentelę „iš apačios į viršų“?

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

Kuriuos du dalykus reikia parodyti, norint įrodyti, kad sprendimo uždavinys X yra NP-pilnas?

  1. AX redukuojamas į P uždavinį, ir X priklauso NP
  2. BX priklauso P, ir X redukuojamas į SAT
  3. CX neturi polinominio algoritmo, ir X yra išsprendžiamas
  4. DX priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
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. BJis veikia tik su nekryptiniais grafais
  3. CViršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią
  4. DTies kiekviena neigiama briauna jis patenka į begalinį ciklą

Atsakymai

  1. 1. A · Tiesinis
  2. 2. B · O(n + k)
  3. 3. C · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  4. 4. A · O(n log n + k log n)
  5. 5. B · Apie log₂ n
  6. 6. B · O(n)
  7. 7. D · X priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  8. 8. C · 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.