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 tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

Ko dvejetainė paieška reikalauja iš savo įvesties?

  1. AMasyve turi būti tik teigiami skaičiai
  2. BMasyvo ilgis turi būti dvejeto laipsnis
  3. CMasyve turi būti ne daugiau kaip 1000 elementų
  4. DMasyvas turi būti surikiuotas
3.Lengvas

Kuris iš šių auga lėčiausiai, kai n tampa didelis?

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

Kam lygus rekurentinės lygties T(n) = T(n − 1) + O(n) sprendinys?

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

Kuris algoritmas randa trumpiausius kelius iš vienos pradinės viršūnės grafe, kurio briaunų svoriai neneigiami?

  1. AVisais atvejais būtinas Belmano–Fordo algoritmas
  2. BKruskalo algoritmas
  3. CPaieška gilyn (DFS)
  4. DDijkstros algoritmas
6.Vidutinis

Paieška platyn nesvoriniame grafe randa:

  1. AMinimalų jungiamąjį medį
  2. BTopologinę tvarką bet kuriame grafe
  3. CTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
  4. DTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
7.Sunkus

Rikiavimas įterpimu surikiuotai įvesčiai veikia per O(n). Ar tai prieštarauja rikiavimo palyginimais apatiniam rėžiui Ω(n log n)?

  1. ATaip, bet tik trumpesniems nei 100 masyvams
  2. BNe, apatinis rėžis taikomas blogiausiam atvejui tarp visų įvesčių, o ne kiekvienai įvesčiai
  3. CTaip, todėl apatinis rėžis neteisingas
  4. DNe, nes rikiavimas įterpimu nėra rikiavimas palyginimais
8.Sunkus

Taikant pagrindinę teoremą (master theorem), T(n) = 8T(n/2) + O(n²) sprendinys yra:

  1. AΘ(n³)
  2. BΘ(n² log n)
  3. CΘ(n²)
  4. DΘ(n log n)

Atsakymai

  1. 1. D · O(n)
  2. 2. D · Masyvas turi būti surikiuotas
  3. 3. B · O(log n)
  4. 4. B · O(n²)
  5. 5. D · Dijkstros algoritmas
  6. 6. D · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  7. 7. B · Ne, apatinis rėžis taikomas blogiausiam atvejui tarp visų įvesčių, o ne kiekvienai įvesčiai
  8. 8. A · Θ(n³)

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