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 rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

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

Koks yra paieškos gilyn laiko sudėtingumas grafui, saugomam gretimumo sąrašais?

  1. AO(V²)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(E log V)
3.Lengvas

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

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

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

  1. AO(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n log n)
5.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(n + k)
  3. CO(nk)
  4. DO(k n log n)
6.Vidutinis

Koks yra standartinio dinaminio programavimo algoritmo, ieškančio m ir n ilgio eilučių ilgiausio bendro posekio, laiko sudėtingumas?

  1. AO(2m+n)
  2. BO(mn)
  3. CO(mn log n)
  4. DO(m + n)
7.Sunkus

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

  1. ADvejetainei paieškai reikia bent dvigubai daugiau atminties
  2. BSusietojo sąrašo mazgų palyginimai lėtesni
  3. CSusietųjų sąrašų negalima surikiuoti
  4. DIki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
8.Sunkus

Ką nustatė Cooko–Levino teorema?

  1. AKiekvieną NP uždavinį galima išspręsti per eksponentinį laiką
  2. BLoginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  3. CStabdymo problema yra neišsprendžiama
  4. DP nelygu NP

Atsakymai

  1. 1. C · O(n log n)
  2. 2. C · O(V + E)
  3. 3. D · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  4. 4. B · O(log n)
  5. 5. A · O(n log n + k log n)
  6. 6. B · O(mn)
  7. 7. D · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  8. 8. B · Loginio įvykdomumo uždavinys (SAT) yra NP-pilnas

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