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

Kaip vadinamas O(2ⁿ) augimas?

  1. ATiesinis
  2. BEksponentinis
  3. CLogaritminis
  4. DPolinominis
2.Lengvas

Kuris iš šių vykdymo laikų yra polinominis?

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

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

  1. ADidysis O
  2. BDidžioji Teta
  3. CDidžioji Omega
  4. DMažoji omega
4.Vidutinis

Koks yra LSD pozicinio rikiavimo (radix sort) vykdymo laikas n sveikųjų skaičių, turinčių d skaitmenų k pagrindo sistemoje?

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

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

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

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

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

Topologinis rikiavimas galimas tik:

  1. ANekryptiniams grafams
  2. BKryptiniams acikliniams grafams
  3. CGrafams su neigiamais svoriais
  4. DPilniesiems grafams
8.Sunkus

Kuris algoritmas randa minimalų jungiamąjį medį, pakartotinai pridėdamas pigiausią briauną, kuri nesudaro ciklo?

  1. AFloido–Voršalo algoritmas
  2. BPrimo algoritmas, pradedant nuo vienos viršūnės
  3. CDijkstros algoritmas
  4. DKruskalo algoritmas

Atsakymai

  1. 1. B · Eksponentinis
  2. 2. C · O(n³)
  3. 3. A · Didysis O
  4. 4. C · O(d(n + k))
  5. 5. D · O(n²)
  6. 6. C · Taip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  7. 7. B · Kryptiniams acikliniams grafams
  8. 8. D · Kruskalo algoritmas

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