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ą apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ATikėtiną laiką su atsitiktine n dydžio įvestimi
  2. BLaiką lėtame kompiuteryje
  3. CDidžiausią laiką tarp visų n dydžio įvesčių
  4. DLaiką su mažiausia įvestimi
2.Lengvas

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

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

Kuris žymėjimas nusako apatinį augimo rėžį?

  1. Ao (mažasis o)
  2. BΩ (didžioji Omega)
  3. CO (didysis O)
  4. DΘ (didžioji Teta)
4.Vidutinis

Kuris teiginys apie rekursinę funkciją be pasiekiamo bazinio atvejo teisingas?

  1. AJi automatiškai grąžina 0
  2. BJi vis kviečia save, kol perpildomas kvietimų stekas
  3. CJi veikia per O(1) laiką
  4. DKompiliatorius visada ją paverčia ciklu, kuris saugiai pasibaigia
5.Vidutinis

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Kuris teiginys apie k-ojo mažiausio nesurikiuoto masyvo elemento išrinkimą teisingas?

  1. AQuickselect blogiausiu atveju veikia per O(log n), nes rekursija vyksta tik į vieną atramos elemento pusę
  2. BIšrinkimas įmanomas tik per O(n²)
  3. CIšrinkimui visada reikia Ω(n log n), nes reikia rikiavimo
  4. DQuickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju
8.Sunkus

Kokia amortizuotoji dvejetainio skaitiklio padidinimo kaina, žinant, kad vienas padidinimas gali pakeisti daug bitų?

  1. AO(1) vienam padidinimui
  2. BO(log n) vienam padidinimui
  3. CO(n) vienam padidinimui
  4. DO(n log n) vienam padidinimui

Atsakymai

  1. 1. C · Didžiausią laiką tarp visų n dydžio įvesčių
  2. 2. A · O(log n)
  3. 3. B · Ω (didžioji Omega)
  4. 4. B · Ji vis kviečia save, kol perpildomas kvietimų stekas
  5. 5. B · O(n)
  6. 6. C · O(log n)
  7. 7. D · Quickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju
  8. 8. A · O(1) vienam padidinimui

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