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

Kokie yra trys „skaldyk ir valdyk“ algoritmo žingsniai?

  1. ASkaityk, skaičiuok, rašyk
  2. BPadalyk, išspręsk, sujunk
  3. CSurikiuok, ieškok, grąžink
  4. DSpėk, tikrink, kartok
2.Lengvas

Kas yra perrinkimo (brute force) algoritmas?

  1. AAlgoritmas, išbandantis visus galimus kandidatinius sprendinius
  2. BAlgoritmas, veikiantis daugelyje procesorių
  3. CAlgoritmas, kuris visada naudoja rekursiją
  4. DAlgoritmas, atsitiktinai spėjantis atsakymą
3.Lengvas

Ciklas pradeda nuo i = 1 ir kiekvienoje iteracijoje padvigubina i, kol i > n. Kiek iteracijų jis atlieka?

  1. AApie n²
  2. BApie log₂ n
  3. CApie n / 2
  4. DApie 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)
  2. BO(log n)
  3. CO(n²)
  4. DO(n log n)
5.Vidutinis

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Koks yra greitojo rikiavimo (quicksort) laiko sudėtingumas blogiausiu atveju?

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

Kaip Bellmano–Fordo algoritmas aptinka iš šaltinio pasiekiamą neigiamo svorio ciklą?

  1. AJis du kartus paleidžia Dijkstros algoritmą ir palygina abu atstumų rezultatus
  2. BJis suskaičiuoja ciklus paieška gilyn
  3. CJis patikrina, ar kuri nors briauna turi neigiamą svorį
  4. DPo V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
8.Sunkus

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

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

Atsakymai

  1. 1. B · Padalyk, išspręsk, sujunk
  2. 2. A · Algoritmas, išbandantis visus galimus kandidatinius sprendinius
  3. 3. B · Apie log₂ n
  4. 4. D · O(n log n)
  5. 5. B · O(n)
  6. 6. B · O(n²)
  7. 7. D · Po V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
  8. 8. A · Θ(nlog₂ 3), apie n1,585

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