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

Ką apibūdina vykdymo laikas vidutiniu atveju?

  1. ALaiką vidutinio ilgio įvesčiai
  2. BLaiką labiausiai paplitusiame kompiuteryje
  3. CTikėtiną laiką esant tam tikram n dydžio įvesčių skirstiniui
  4. DVidurinę reikšmę tarp geriausio ir blogiausio atvejo vykdymo laikų
2.Lengvas

Kaip vadinamas O(2ⁿ) augimas?

  1. ATiesinis
  2. BPolinominis
  3. CLogaritminis
  4. DEksponentinis
3.Lengvas

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

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

  1. AO(n log n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
5.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 3 monetas; optimalus sprendinys – 2
  2. BGodusis panaudoja 3 monetas; optimalus sprendinys – 3
  3. CGodusis panaudoja 4 monetas; optimalus sprendinys – 3
  4. DGodusis panaudoja 2 monetas; optimalus sprendinys – 2
6.Vidutinis

Ką apskaičiuoja Floydo–Warshallo algoritmas ir kaip greitai?

  1. AMinimalų jungiamąjį medį per O(E log V)
  2. BTrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)
  3. CTrumpiausius kelius tarp visų viršūnių porų per O(V³)
  4. DTopologinę tvarką per O(V²)
7.Sunkus

Ką nustatė Cooko–Levino teorema?

  1. AKiekvieną NP uždavinį galima išspręsti per eksponentinį laiką
  2. BP nelygu NP
  3. CStabdymo problema yra neišsprendžiama
  4. DLoginio įvykdomumo uždavinys (SAT) yra NP-pilnas
8.Sunkus

Kuriam kuprinės uždavinio variantui godžioji taisyklė „imti daiktus pagal vertės ir svorio santykį“ visada duoda optimalų atsakymą?

  1. AAbiem variantams
  2. B0/1 kuprinei, kai daiktai visada imami ištisi
  3. CNė vienam variantui
  4. DTrupmeninei kuprinei, kai daiktus galima dalyti

Atsakymai

  1. 1. C · Tikėtiną laiką esant tam tikram n dydžio įvesčių skirstiniui
  2. 2. D · Eksponentinis
  3. 3. B · O(1)
  4. 4. D · O(n)
  5. 5. A · Godusis panaudoja 3 monetas; optimalus sprendinys – 2
  6. 6. C · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  7. 7. D · Loginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  8. 8. D · Trupmeninei kuprinei, kai daiktus galima dalyti

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