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

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

  1. APastovus
  2. BLogaritminis
  3. CTiesinis
  4. DKvadratinis
3.Lengvas

Koks yra dvejetainės paieškos surikiuotame masyve laiko sudėtingumas?

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

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

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

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

  1. ATrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)
  2. BTopologinę tvarką per O(V²)
  3. CMinimalų jungiamąjį medį per O(E log V)
  4. DTrumpiausius kelius tarp visų viršūnių porų per O(V³)
6.Vidutinis

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu masyvu, kurio visi elementai skirtingi
  2. BSu 2 ilgio masyvu
  3. CSu atsitiktinės tvarkos masyvu
  4. DSu jau surikiuotu masyvu
7.Sunkus

Kuris iš šių įvykdomumo uždavinių, kaip žinoma, išsprendžiamas per polinominį laiką?

  1. ALoginės schemos įvykdomumas
  2. B3-SAT, kai kiekviename disjunkte yra lygiai trys literalai
  3. CBendrasis SAT konjunkcinės normaliosios formos formulėms
  4. D2-SAT, kai kiekviename disjunkte yra daugiausia du literalai
8.Sunkus

Karacubos daugyba tenkina T(n) = 3T(n/2) + O(n). Kam lygus sprendinys?

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n3)
  4. DΘ(nlog₂ 3), apie n1,585

Atsakymai

  1. 1. C · O(n)
  2. 2. C · Tiesinis
  3. 3. D · O(log n)
  4. 4. A · O(n log n)
  5. 5. D · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  6. 6. D · Su jau surikiuotu masyvu
  7. 7. D · 2-SAT, kai kiekviename disjunkte yra daugiausia du literalai
  8. 8. D · Θ(nlog₂ 3), apie n1,585

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