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 tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

Kiek papildomos atminties naudoja standartinis masyvu grįstas rikiavimas suliejimu?

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

Koks yra dvejetainės paieškos surikiuotame masyve laiko sudėtingumas?

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

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

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

Rekurentinės lygties T(n) = 2T(n/2) + O(n) sprendinys yra:

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

Maždaug kiek palyginimų blogiausiu atveju reikia dvejetainei paieškai surikiuotame 1,000,000 elementų masyve?

  1. AApie 20
  2. BApie 500,000
  3. CApie 1,000
  4. DApie 100
7.Sunkus

Kodėl dvejetainė paieška vienkrypčiame susietajame sąraše neužtikrina O(log n) laiko?

  1. AIki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  2. BDvejetainei paieškai reikia bent dvigubai daugiau atminties
  3. CSusietųjų sąrašų negalima surikiuoti
  4. DSusietojo sąrašo mazgų palyginimai lėtesni
8.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 NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  3. CX priklauso P, ir X redukuojamas į SAT
  4. DX neturi polinominio algoritmo, ir X yra išsprendžiamas

Atsakymai

  1. 1. D · O(n)
  2. 2. B · O(n)
  3. 3. C · O(log n)
  4. 4. A · Su jau surikiuotu masyvu
  5. 5. C · O(n log n)
  6. 6. A · Apie 20
  7. 7. A · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  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.