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(E log V)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
2.Lengvas

Koks yra 3n² + 5n + 2 didysis O?

  1. AO(3n²)
  2. BO(n³)
  3. CO(5n)
  4. DO(n²)
3.Lengvas

Kaip veikia rikiavimas išrinkimu?

  1. AJis padalija masyvą pusiau ir sulieja puses
  2. BJis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  3. CJis pakartotinai sukeičia neteisinga tvarka esančius gretimus elementus
  4. DJis kiekvieną elementą postūmiais įterpia į augančią surikiuotą dalį
4.Vidutinis

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

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

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

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

Paieška platyn nesvoriniame grafe randa:

  1. AMinimalų jungiamąjį medį
  2. BTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  3. CTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
  4. DTopologinę tvarką bet kuriame grafe
7.Sunkus

Paėmus abu kiekvienos maksimalaus poravimo (maximal matching) briaunos galus, gaunamas viršūnių denginys. Koks geras šis denginys?

  1. ADaugiausia log n kartų didesnis už minimalų
  2. BVisada minimalus viršūnių denginys
  3. CDaugiausia dvigubai didesnis už minimalų viršūnių denginį
  4. DNežinomos kokybės, palyginti su optimaliu
8.Sunkus

Ką nustatė Cooko–Levino teorema?

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

Atsakymai

  1. 1. B · O(V + E)
  2. 2. D · O(n²)
  3. 3. B · Jis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  4. 4. C · Su jau surikiuotu masyvu
  5. 5. D · O(n²)
  6. 6. B · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  7. 7. C · Daugiausia dvigubai didesnis už minimalų viršūnių denginį
  8. 8. C · Loginio įvykdomumo uždavinys (SAT) yra NP-pilnas

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