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

Algoritmo vykdymo laikas yra O(n). Kaip vadinamas toks augimas?

  1. ALogaritminis
  2. BTiesinis
  3. CPastovus
  4. DKvadratinis
2.Lengvas

Kam lygus log₂ 1024?

  1. A32
  2. B512
  3. C12
  4. D10
3.Lengvas

Kuris rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

  1. ARikiavimas suliejimu
  2. BBurbuliuko rikiavimas
  3. CRikiavimas įterpimu
  4. DGreitasis rikiavimas (quicksort)
4.Vidutinis

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

  1. ARikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
  2. BRikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  3. CRekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų
  4. DRikiavimas įterpimu blogiausiu atveju yra O(n log n)
5.Vidutinis

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

  1. AO(log n)
  2. BO(n²)
  3. CO(n)
  4. DO(n log 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(log n)
  3. CO(n)
  4. DO(2ⁿ)
7.Sunkus

Kaip dideliems n palyginami n! ir 2ⁿ?

  1. An! yra O(n²)
  2. B2ⁿ auga greičiau už n!
  3. CJie auga vienodu greičiu
  4. Dn! auga greičiau už 2ⁿ
8.Sunkus

Koks yra dvejetainės krūvos sudarymo iš n nesurikiuotų elementų metodu „iš apačios į viršų“ (bottom-up) laiko sudėtingumas?

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

Atsakymai

  1. 1. B · Tiesinis
  2. 2. D · 10
  3. 3. D · Greitasis rikiavimas (quicksort)
  4. 4. B · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  5. 5. D · O(n log n)
  6. 6. C · O(n)
  7. 7. D · n! auga greičiau už 2ⁿ
  8. 8. A · O(n)

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