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

O(n²) algoritmas, kai n = 1000, trunka 1 sekundę. Maždaug kiek jis truks, kai n = 2000?

  1. A1 sekundę
  2. B4 sekundes
  3. C8 sekundes
  4. D2 sekundes
2.Lengvas

Koks yra rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

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

Kuris rikiavimo algoritmas pakartotinai sukeičia vietomis gretimus elementus, esančius netinkama tvarka?

  1. ABurbuliuko rikiavimas
  2. BRikiavimas suliejimu
  3. CRikiavimas krūva
  4. DGreitasis rikiavimas (quicksort)
4.Vidutinis

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu jau surikiuotu masyvu
  2. BSu 2 ilgio masyvu
  3. CSu atsitiktinės tvarkos masyvu
  4. DSu masyvu, kurio visi elementai skirtingi
5.Vidutinis

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

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

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

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

Trumpiausius paprastuosius kelius galima rasti per polinominį laiką. Kas žinoma apie ilgiausio paprastojo kelio tarp dviejų viršūnių paiešką bendrajame grafe?

  1. AJis neišsprendžiamas
  2. BJis visada išsprendžiamas per O(V + E)
  3. CTai NP-sunkus uždavinys
  4. DJį galima išspręsti Dijkstros algoritmu su priešingo ženklo svoriais
8.Sunkus

Ką reikia padaryti, norint parodyti, kad naujas uždavinys X yra NP-sunkus?

  1. APer polinominį laiką redukuoti X į žinomą NP-sunkų uždavinį
  2. BParodyti, kad X neturi polinominio algoritmo mažoms įvestims
  3. CPer polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X
  4. DParodyti, kad X galima patikrinti per polinominį laiką

Atsakymai

  1. 1. B · 4 sekundes
  2. 2. A · O(n log n)
  3. 3. A · Burbuliuko rikiavimas
  4. 4. A · Su jau surikiuotu masyvu
  5. 5. A · O(log n)
  6. 6. D · O(n²)
  7. 7. C · Tai NP-sunkus uždavinys
  8. 8. C · Per polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X

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