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ą apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ADidžiausią laiką tarp visų n dydžio įvesčių
  2. BTikėtiną laiką su atsitiktine n dydžio įvestimi
  3. CLaiką lėtame kompiuteryje
  4. DLaiką su mažiausia įvestimi
2.Lengvas

Kokį sudėtingumą paprastai turi algoritmas su dviem įdėtiniais ciklais, kurių kiekvienas vykdomas n kartų?

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

Kuris rikiavimo algoritmas pakartotinai sukeičia vietomis gretimus elementus, esančius netinkama tvarka?

  1. ARikiavimas suliejimu
  2. BBurbuliuko rikiavimas
  3. CRikiavimas krūva
  4. DGreitasis rikiavimas (quicksort)
4.Vidutinis

Kodėl dinaminis programavimas realiai nepagreitina rikiavimo suliejimu?

  1. ARikiavimas suliejimu jau yra O(n)
  2. BDinaminis programavimas veikia tik su grafų uždaviniais, bet ne su masyvais
  3. CJo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  4. DRikiavimas suliejimu neturi rekursinės struktūros
5.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 log n)
  4. DO(n)
6.Vidutinis

Funkcija vykdo vieną n iteracijų ciklą, o paskui, atskirai, dar vieną n iteracijų ciklą. Koks jos laiko sudėtingumas?

  1. AO(n²)
  2. BO(n)
  3. CO(2ⁿ)
  4. DO(log n)
7.Sunkus

Kuris P klasės apibrėžimas teisingas?

  1. AUždaviniai, kuriems bet kuriame kompiuteryje reikia eksponentinio laiko
  2. BSprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per polinominį laiką
  3. CUždaviniai, kuriuos galima spręsti lygiagrečiai
  4. DUždaviniai, kurių sprendinius galima patikrinti, bet niekada nerasti per polinominį laiką
8.Sunkus

Kokios yra n-tojo Fibonačio skaičiaus skaičiavimo ciklu, saugančiu tik dvi paskutines reikšmes, laiko ir atminties sąnaudos?

  1. AO(log n) laiko ir O(n) atminties
  2. BO(2ⁿ) laiko ir O(1) atminties
  3. CO(n) laiko ir O(1) atminties
  4. DO(n) laiko ir O(n) atminties

Atsakymai

  1. 1. A · Didžiausią laiką tarp visų n dydžio įvesčių
  2. 2. B · O(n²)
  3. 3. B · Burbuliuko rikiavimas
  4. 4. C · Jo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  5. 5. B · O(n²)
  6. 6. B · O(n)
  7. 7. B · Sprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per polinominį laiką
  8. 8. C · O(n) laiko ir O(1) atminties

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