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 rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

Ką reiškia, jei operacija atliekama per O(1) laiką?

  1. AJą galima vykdyti tik vieną kartą
  2. BJi apdoroja lygiai vieną elementą per vykdymo sekundę
  3. CJos vykdymo laikas nedidėja didėjant įvesties dydžiui
  4. DJi visada trunka lygiai vieną sekundę
3.Lengvas

Koks yra 3n² + 5n + 2 didysis O?

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

Palyginimais pagrįsto rikiavimo apatinis rėžis blogiausiu atveju yra:

  1. AΩ(n log n)
  2. BΩ(n²)
  3. CΩ(log n)
  4. DΩ(n)
5.Vidutinis

Koks yra Bellmano–Fordo algoritmo laiko sudėtingumas grafui su V viršūnių ir E briaunų?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(V³ × E)
  4. DO(E log V)
6.Vidutinis

Turint 1, 3 ir 4 vertės monetas ir 6 sumą, kiek monetų panaudoja godusis metodas „pirmiausia didžiausia moneta“, palyginti su optimaliu sprendiniu?

  1. AGodusis panaudoja 2 monetas; optimalus sprendinys – 2
  2. BGodusis panaudoja 3 monetas; optimalus sprendinys – 2
  3. CGodusis panaudoja 4 monetas; optimalus sprendinys – 3
  4. DGodusis panaudoja 3 monetas; optimalus sprendinys – 3
7.Sunkus

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

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

Kuris teiginys apie k-ojo mažiausio nesurikiuoto masyvo elemento išrinkimą teisingas?

  1. AIšrinkimas įmanomas tik per O(n²)
  2. BQuickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju
  3. CIšrinkimui visada reikia Ω(n log n), nes reikia rikiavimo
  4. DQuickselect blogiausiu atveju veikia per O(log n), nes rekursija vyksta tik į vieną atramos elemento pusę

Atsakymai

  1. 1. C · O(n)
  2. 2. C · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  3. 3. C · O(n²)
  4. 4. A · Ω(n log n)
  5. 5. A · O(V × E)
  6. 6. B · Godusis panaudoja 3 monetas; optimalus sprendinys – 2
  7. 7. C · n = o(n²), bet n nėra o(n)
  8. 8. B · Quickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju

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