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

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

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

Ką reiškia, jei operacija atliekama per O(1) laiką?

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

Kas yra memoizacija?

  1. AFunkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
  2. BAutomatinis rekursijos pavertimas ekvivalenčiu ciklu, kad nebereikėtų kvietimų steko
  3. CKomentarų rašymas prie kiekvienos kodo eilutės
  4. DAtminties atlaisvinimas funkcijai grįžus
4.Vidutinis

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

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

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

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

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

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

Uždavinys yra NP-pilnas, jei jis:

  1. APriklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką
  2. BNepriklauso NP, bet yra sunkesnis už visus NP uždavinius, pvz., sustojimo problema
  3. CIšsprendžiamas per polinominį laiką
  4. DNeišsprendžiamas
8.Sunkus

Kodėl bet kuriai palyginimais pagrįstai paieškai surikiuotame masyve blogiausiu atveju reikia Ω(log n) palyginimų?

  1. ADvejetainė paieška yra vienintelis galimas algoritmas, ir jam reikia log₂ n palyginimų
  2. BKiekvienas palyginimas trunka logaritminį laiką
  3. CSprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
  4. DKiekvieną elementą reikia palyginti bent kartą

Atsakymai

  1. 1. C · O(log n)
  2. 2. B · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  3. 3. A · Funkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
  4. 4. C · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  5. 5. D · O(n log n)
  6. 6. A · O(n²)
  7. 7. A · Priklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką
  8. 8. C · Sprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n

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