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 suliejimu laiko sudėtingumas blogiausiu atveju?

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

Kaip vadinamas O(2ⁿ) augimas?

  1. ALogaritminis
  2. BPolinominis
  3. CEksponentinis
  4. DTiesinis
3.Lengvas

Kuris rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

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

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

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

Ką apskaičiuoja Floydo–Warshallo algoritmas ir kaip greitai?

  1. ATrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)
  2. BTrumpiausius kelius tarp visų viršūnių porų per O(V³)
  3. CMinimalų jungiamąjį medį per O(E log V)
  4. DTopologinę tvarką per O(V²)
6.Vidutinis

Ką matuoja amortizuotoji analizė?

  1. AVidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
  2. BTikėtiną kainą su atsitiktinėmis įvestimis
  3. CVienos brangiausios operacijos bet kurioje sekos vietoje kainą
  4. DAlgoritmo kainą su geriausia įvestimi
7.Sunkus

Heldo–Karpo dinaminio programavimo algoritmas tiksliai išsprendžia keliaujančio pirklio uždavinį. Koks jo vykdymo laikas n miestų?

  1. AO(n³)
  2. BO(2n²)
  3. CO(n² 2ⁿ)
  4. DO(n!)
8.Sunkus

Kuris teiginys apie P ir NP yra teisingas?

  1. AKiekvienas P klasės uždavinys taip pat priklauso NP
  2. BNP uždavinių sprendinių negalima greitai patikrinti
  3. CĮrodyta, kad P ≠ NP
  4. DNP reiškia „nepolinominis“ (not polynomial)

Atsakymai

  1. 1. B · O(n log n)
  2. 2. C · Eksponentinis
  3. 3. D · Greitasis rikiavimas (quicksort)
  4. 4. A · Apie 20
  5. 5. B · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  6. 6. A · Vidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
  7. 7. C · O(n² 2ⁿ)
  8. 8. A · Kiekvienas P klasės uždavinys taip pat priklauso NP

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