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ą reiškia, jei operacija atliekama per O(1) laiką?

  1. AJos vykdymo laikas nedidėja didėjant įvesties dydžiui
  2. BJi visada trunka lygiai vieną sekundę
  3. CJi apdoroja lygiai vieną elementą per vykdymo sekundę
  4. DJą galima vykdyti tik vieną kartą
2.Lengvas

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

  1. ADidžioji Teta
  2. BDidžioji Omega
  3. CMažoji omega
  4. DDidysis O
3.Lengvas

Kaip veikia rikiavimas išrinkimu?

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

Ką reiškia, kad uždavinys turi optimalią struktūrą (optimal substructure)?

  1. AOptimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  2. BUždavinį galima išspręsti per pastovų laiką
  3. CUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai
  4. DVisi daliniai uždaviniai yra vienodo dydžio
5.Vidutinis

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

  1. ARekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų
  2. BRikiavimas įterpimu blogiausiu atveju yra O(n log n)
  3. CRikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  4. DRikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
6.Vidutinis

Rekurentinės lygties T(n) = 2T(n/2) + O(n) sprendinys yra:

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

Kuriuos du dalykus reikia parodyti, norint įrodyti, kad sprendimo uždavinys X yra NP-pilnas?

  1. AX redukuojamas į P uždavinį, ir X priklauso NP
  2. BX neturi polinominio algoritmo, ir X yra išsprendžiamas
  3. CX priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  4. DX priklauso P, ir X redukuojamas į SAT
8.Sunkus

Trumpiausius paprastuosius kelius galima rasti per polinominį laiką. Kas žinoma apie ilgiausio paprastojo kelio tarp dviejų viršūnių paiešką bendrajame grafe?

  1. AJį galima išspręsti Dijkstros algoritmu su priešingo ženklo svoriais
  2. BJis visada išsprendžiamas per O(V + E)
  3. CJis neišsprendžiamas
  4. DTai NP-sunkus uždavinys

Atsakymai

  1. 1. A · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  2. 2. D · Didysis O
  3. 3. D · Jis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  4. 4. A · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  5. 5. C · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  6. 6. C · O(n log n)
  7. 7. C · X priklauso NP, ir žinomas NP-pilnas uždavinys per polinominį laiką redukuojamas į X
  8. 8. D · Tai NP-sunkus uždavinys

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