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 3n² + 5n + 2 didysis O?

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

Kuri sudėtingumo klasė auga greičiausiai, kai n didelis?

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

Kas yra rekursija?

  1. ARikiavimo metodas
  2. BCiklas, kuris niekada nesibaigia
  3. CFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. DDuomenų struktūros tipas
4.Vidutinis

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Ar teisinga sakyti, kad O(n²) algoritmas yra ir O(n³)?

  1. ANe, nes didysis O visada turi nurodyti tikslų funkcijos augimo greitį
  2. BTaip, bet tik jei n mažesnis už 100
  3. CNe, nes dideliems n n³ mažesnis už n²
  4. DTaip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
6.Vidutinis

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

  1. AO(n²)
  2. BO(log n)
  3. CO(n)
  4. DO(n log n)
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. B2n = o(n), nes 2n auga lėtai
  3. Cn² = o(n)
  4. Dn = o(n²), bet n nėra o(n)
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. BIki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  3. CSusietųjų sąrašų negalima surikiuoti
  4. DDvejetainei paieškai reikia bent dvigubai daugiau atminties

Atsakymai

  1. 1. D · O(n²)
  2. 2. C · O(2ⁿ)
  3. 3. C · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. 4. B · O(n)
  5. 5. D · Taip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  6. 6. D · O(n log n)
  7. 7. D · n = o(n²), bet n nėra o(n)
  8. 8. B · 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.