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 paieškos gilyn laiko sudėtingumas grafui, saugomam gretimumo sąrašais?

  1. AO(V + E)
  2. BO(V²)
  3. CO(V × E)
  4. DO(E log V)
2.Lengvas

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

  1. AApie n²
  2. BApie n / 2
  3. CApie n
  4. DApie log₂ n
3.Lengvas

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

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

Kodėl dinaminis programavimas realiai nepagreitina rikiavimo suliejimu?

  1. ARikiavimas suliejimu jau yra O(n)
  2. BRikiavimas suliejimu neturi rekursinės struktūros
  3. CJo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  4. DDinaminis programavimas veikia tik su grafų uždaviniais, bet ne su masyvais
6.Vidutinis

Ką matuoja amortizuotoji analizė?

  1. AVienos brangiausios operacijos bet kurioje sekos vietoje kainą
  2. BVidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
  3. CAlgoritmo kainą su geriausia įvestimi
  4. DTikėtiną kainą su atsitiktinėmis įvestimis
7.Sunkus

Koks yra dvejetainės krūvos sudarymo iš n nesurikiuotų elementų metodu „iš apačios į viršų“ (bottom-up) laiko sudėtingumas?

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

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

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

Atsakymai

  1. 1. A · O(V + E)
  2. 2. D · Apie log₂ n
  3. 3. C · O(log n)
  4. 4. C · O(n)
  5. 5. C · Jo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  6. 6. B · Vidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
  7. 7. A · O(n)
  8. 8. A · Po V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti

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