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

Kokie yra trys „skaldyk ir valdyk“ algoritmo žingsniai?

  1. ASkaityk, skaičiuok, rašyk
  2. BSurikiuok, ieškok, grąžink
  3. CSpėk, tikrink, kartok
  4. DPadalyk, išspręsk, sujunk
2.Lengvas

Ciklas pradeda nuo i = 1 ir kiekvienoje iteracijoje padvigubina i, kol i > n. Kiek iteracijų jis atlieka?

  1. AApie n²
  2. BApie n
  3. CApie n / 2
  4. DApie log₂ n
3.Lengvas

Kas yra rekursija?

  1. ADuomenų struktūros tipas
  2. BFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  3. CRikiavimo metodas
  4. DCiklas, kuris niekada nesibaigia
4.Vidutinis

Koks yra amortizuotas laiko sudėtingumas pridedant elementą į dinaminio masyvo, kuris prisipildęs padvigubina savo talpą, galą?

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

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

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

Kuris rikiavimo algoritmas yra stabilus?

  1. AGreitasis rikiavimas (įprasta versija vietoje)
  2. BRikiavimas krūva
  3. CRikiavimas suliejimu
  4. DRikiavimas išrinkimu (įprasta versija)
7.Sunkus

Koks yra Dijkstros algoritmo su dvejetaine krūva vykdymo laikas grafui su V viršūnių ir E briaunų?

  1. AO(V × E)
  2. BO(V³)
  3. CO((V + E) log V)
  4. DO(V + E)
8.Sunkus

Kas išplauktų, jei kas nors rastų polinominio laiko algoritmą vienam NP-pilnam uždaviniui?

  1. AVisi eksponentinio laiko algoritmai nedelsiant imtų veikti tiesiniu laiku
  2. BKiekvieną NP uždavinį būtų galima išspręsti per polinominį laiką, taigi P = NP
  3. CStabdymo problema taptų išsprendžiama
  4. DTik tas vienas uždavinys pereitų į P

Atsakymai

  1. 1. D · Padalyk, išspręsk, sujunk
  2. 2. D · Apie log₂ n
  3. 3. B · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. 4. A · O(1)
  5. 5. C · O(n log n)
  6. 6. C · Rikiavimas suliejimu
  7. 7. C · O((V + E) log V)
  8. 8. B · Kiekvieną NP uždavinį būtų galima išspręsti per polinominį laiką, taigi P = NP

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