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

Kam lygus log₂ 1024?

  1. A12
  2. B512
  3. C10
  4. D32
2.Lengvas

Kas yra algoritmas?

  1. ADuomenų struktūra, sauganti skaičius
  2. BBet kokia kompiuterio programa su grafine sąsaja
  3. CProgramavimo kalba, sukurta matematinėms formulėms rašyti
  4. DBaigtinė tiksliai apibrėžtų žingsnių seka, sprendžianti uždavinį
3.Lengvas

Koks yra tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for j = 1 to i: atlikti O(1) darbą?

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

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

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

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

  1. AO(log n)
  2. BO(n log n)
  3. CO(n)
  4. DO(n²)
7.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 P, ir X redukuojamas į SAT
  3. CX priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  4. DX redukuojamas į P uždavinį, ir X priklauso NP
8.Sunkus

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

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n)
  4. DΘ(n log² n)

Atsakymai

  1. 1. C · 10
  2. 2. D · Baigtinė tiksliai apibrėžtų žingsnių seka, sprendžianti uždavinį
  3. 3. A · O(n)
  4. 4. B · O(n²)
  5. 5. B · O(n)
  6. 6. B · O(n log n)
  7. 7. C · X priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  8. 8. D · Θ(n log² n)

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