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 algoritmas?

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

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

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

Ką apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ALaiką su mažiausia įvestimi
  2. BLaiką lėtame kompiuteryje
  3. CTikėtiną laiką su atsitiktine n dydžio įvestimi
  4. DDidžiausią laiką tarp visų n dydžio įvesčių
4.Vidutinis

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

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

Naivaus rekursyvaus Fibonačio skaičių skaičiavimo (fib(n) = fib(n−1) + fib(n−2)) laiko sudėtingumas yra:

  1. APastovus
  2. BLogaritminis
  3. CTiesinis
  4. DEksponentinis
7.Sunkus

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

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

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

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

Atsakymai

  1. 1. D · Baigtinė tiksliai apibrėžtų žingsnių seka, sprendžianti uždavinį
  2. 2. C · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  3. 3. D · Didžiausią laiką tarp visų n dydžio įvesčių
  4. 4. D · O(n log n + k log n)
  5. 5. B · O(mn)
  6. 6. D · Eksponentinis
  7. 7. B · X priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  8. 8. D · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą

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