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

Kas yra rekursija?

  1. ADuomenų struktūros tipas
  2. BCiklas, kuris niekada nesibaigia
  3. CFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. DRikiavimo metodas
2.Lengvas

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

  1. AMažoji omega
  2. BDidysis O
  3. CDidžioji Teta
  4. DDidžioji Omega
3.Lengvas

Kam lygus log₂ 1024?

  1. A12
  2. B10
  3. C512
  4. D32
4.Vidutinis

Paieška platyn nesvoriniame grafe randa:

  1. ATopologinę tvarką bet kuriame grafe
  2. BMinimalų jungiamąjį medį
  3. CTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
  4. DTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
5.Vidutinis

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for j = 1 to i: atlikti O(1) darbą?

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

Kam lygus rekurentinės lygties T(n) = 2T(n/2) + O(1) sprendinys?

  1. AO(n²)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n)
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 log n)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
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. AJis visada išsprendžiamas per O(V + E)
  2. BJis neišsprendžiamas
  3. CTai NP-sunkus uždavinys
  4. DJį galima išspręsti Dijkstros algoritmu su priešingo ženklo svoriais

Atsakymai

  1. 1. C · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  2. 2. B · Didysis O
  3. 3. B · 10
  4. 4. D · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  5. 5. B · O(n²)
  6. 6. D · O(n)
  7. 7. D · O(n)
  8. 8. C · Tai NP-sunkus uždavinys

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