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

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 griežtai greičiau už g
  4. Df auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
2.Lengvas

Erdvės (atminties) sudėtingumas matuoja:

  1. AKiek atminties algoritmui reikia didėjant įvesties duomenims
  2. BFizinį kompiuterio dydį
  3. CProgramos failo užimamą vietą diske jį sukompiliavus
  4. DKodo eilučių skaičių
3.Lengvas

Koks yra rikiavimo skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

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

  1. AEksponentinis
  2. BTiesinis
  3. CPastovus
  4. DLogaritminis
5.Vidutinis

Koks yra amortizuotas laiko sudėtingumas pridedant elementą į dinaminio masyvo, kuris prisipildęs padvigubina savo talpą, galą?

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

Ką reiškia, kad uždavinys turi optimalią struktūrą (optimal substructure)?

  1. AUždavinį galima išspręsti per pastovų laiką
  2. BOptimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  3. CUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai
  4. DVisi daliniai uždaviniai yra vienodo dydžio
7.Sunkus

Kuris teiginys apie mažojo o žymėjimą teisingas?

  1. An = o(n), nes kiekviena funkcija yra mažasis o pati sau
  2. Bn = o(n²), bet n nėra o(n)
  3. Cn² = o(n)
  4. D2n = o(n), nes 2n auga lėtai
8.Sunkus

Topologinis rikiavimas galimas tik:

  1. AKryptiniams acikliniams grafams
  2. BPilniesiems grafams
  3. CNekryptiniams grafams
  4. DGrafams su neigiamais svoriais

Atsakymai

  1. 1. D · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  2. 2. A · Kiek atminties algoritmui reikia didėjant įvesties duomenims
  3. 3. C · O(n + k)
  4. 4. A · Eksponentinis
  5. 5. A · O(1)
  6. 6. B · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  7. 7. B · n = o(n²), bet n nėra o(n)
  8. 8. A · Kryptiniams acikliniams grafams

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