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

Kas yra rekursinės funkcijos bazinis atvejis?

  1. AAtvejis su didžiausia įvestimi, kuris apdorojamas prieš bet kokius rekursinius kvietimus
  2. BAtvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  3. CPirmoji funkcijos eilutė
  4. DKvietimas, naudojantis daugiausia atminties
2.Lengvas

Kuri sudėtingumo klasė auga greičiausiai, kai n didelis?

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

Koks yra didžiausios reikšmės paieškos nesurikiuotame n skaičių masyve laiko sudėtingumas?

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

Kodėl dinaminis programavimas realiai nepagreitina rikiavimo suliejimu?

  1. ARikiavimas suliejimu jau yra O(n)
  2. BDinaminis programavimas veikia tik su grafų uždaviniais, bet ne su masyvais
  3. CJo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  4. DRikiavimas suliejimu neturi rekursinės struktūros
5.Vidutinis

Paieška platyn nesvoriniame grafe randa:

  1. ATopologinę tvarką bet kuriame grafe
  2. BTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  3. CTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
  4. DMinimalų jungiamąjį medį
6.Vidutinis

Dinaminis programavimas naudingas, kai uždavinys turi:

  1. AVisai jokių poproblemių, todėl jį galima išspręsti vienu žingsniu
  2. BTik atsitiktinius įvesties duomenis
  3. CPersidengiančius poproblemius ir optimalią postruktūrą
  4. DVieną ciklą
7.Sunkus

Ką reikia padaryti, norint parodyti, kad naujas uždavinys X yra NP-sunkus?

  1. APer polinominį laiką redukuoti X į žinomą NP-sunkų uždavinį
  2. BParodyti, kad X galima patikrinti per polinominį laiką
  3. CPer polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X
  4. DParodyti, kad X neturi polinominio algoritmo mažoms įvestims
8.Sunkus

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

  1. AX neturi polinominio algoritmo, ir X yra išsprendžiamas
  2. BX priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  3. CX priklauso P, ir X redukuojamas į SAT
  4. DX redukuojamas į P uždavinį, ir X priklauso NP

Atsakymai

  1. 1. B · Atvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  2. 2. A · O(2ⁿ)
  3. 3. D · O(n)
  4. 4. C · Jo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  5. 5. B · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  6. 6. C · Persidengiančius poproblemius ir optimalią postruktūrą
  7. 7. C · Per polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X
  8. 8. B · X priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X

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