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 rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

Kuris iš šių vykdymo laikų yra polinominis?

  1. AO(nⁿ)
  2. BO(2ⁿ)
  3. CO(n³)
  4. DO(n!)
3.Lengvas

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

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

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

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

Maždaug kiek palyginimų blogiausiu atveju reikia dvejetainei paieškai surikiuotame 1,000,000 elementų masyve?

  1. AApie 500,000
  2. BApie 1,000
  3. CApie 20
  4. DApie 100
6.Vidutinis

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

  1. AO(n log n)
  2. BO(1)
  3. CO(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

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

  1. AJis neišsprendžiamas
  2. BSprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
  3. CSprendimo versija priklauso P, bet optimizavimo versija yra NP-pilna
  4. DJis priklauso P, nes jį išsprendžia Dijkstros algoritmas aplankydamas kiekvieną miestą vieną kartą

Atsakymai

  1. 1. B · O(n)
  2. 2. C · O(n³)
  3. 3. A · Apie log₂ n
  4. 4. D · O(n²)
  5. 5. C · Apie 20
  6. 6. C · O(log n)
  7. 7. D · O(n)
  8. 8. B · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki

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