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 rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

  1. ARikiavimas suliejimu
  2. BRikiavimas įterpimu
  3. CBurbuliuko rikiavimas
  4. DGreitasis rikiavimas (quicksort)
2.Lengvas

Koks yra rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

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

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

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

Godusis algoritmas:

  1. AIšbando kiekvieną galimą sprendinį
  2. BKiekviename žingsnyje priima lokaliai geriausią sprendimą
  3. CNaudoja tik rekursiją
  4. DVisada pateikia optimalų sprendinį
5.Vidutinis

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

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

Koks yra standartinio dinaminio programavimo algoritmo, ieškančio m ir n ilgio eilučių ilgiausio bendro posekio, laiko sudėtingumas?

  1. AO(mn log n)
  2. BO(m + n)
  3. CO(mn)
  4. DO(2m+n)
7.Sunkus

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

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

0/1 kuprinės uždavinys, sprendžiamas dinaminiu programavimu, užtrunka O(nW) laiko. Kodėl tai vadinama pseudopolinominiu laiku?

  1. AW yra skaitinė reikšmė, todėl laikas yra eksponentinis bitų, reikalingų W užrašyti, skaičiaus atžvilgiu
  2. BNes n visada mažas
  3. CNes jis veikia tik kai W = 0
  4. DNes algoritmas yra atsitiktinis ir jo vykdymo laikas kinta su kiekviena įvestimi

Atsakymai

  1. 1. D · Greitasis rikiavimas (quicksort)
  2. 2. B · O(n log n)
  3. 3. C · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  4. 4. B · Kiekviename žingsnyje priima lokaliai geriausią sprendimą
  5. 5. B · Apie 20
  6. 6. C · O(mn)
  7. 7. B · Sprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
  8. 8. A · W yra skaitinė reikšmė, todėl laikas yra eksponentinis bitų, reikalingų W užrašyti, skaičiaus atžvilgiu

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