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ą 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. CJą galima vykdyti tik vieną kartą
  4. DJos vykdymo laikas nedidėja didėjant įvesties dydžiui
2.Lengvas

Kas yra rekursinės funkcijos bazinis atvejis?

  1. APirmoji funkcijos eilutė
  2. BKvietimas, naudojantis daugiausia atminties
  3. CAtvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  4. DAtvejis su didžiausia įvestimi, kuris apdorojamas prieš bet kokius rekursinius kvietimus
3.Lengvas

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

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

Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?

  1. APirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
  2. BPirmiausia pasirinkti trumpiausią veiklą
  3. CPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  4. DPasirinkti anksčiausiai prasidedančią veiklą
5.Vidutinis

Paieška platyn nesvoriniame grafe randa:

  1. AMinimalų jungiamąjį medį
  2. BTopologinę tvarką bet kuriame grafe
  3. CTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  4. DTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
6.Vidutinis

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

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

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

  1. AJis neišsprendžiamas
  2. BSprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
  3. CJis priklauso P, nes jį išsprendžia Dijkstros algoritmas aplankydamas kiekvieną miestą vieną kartą
  4. DSprendimo versija priklauso P, bet optimizavimo versija yra NP-pilna
8.Sunkus

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

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

Atsakymai

  1. 1. D · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  2. 2. C · Atvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  3. 3. B · O(log n)
  4. 4. C · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  5. 5. C · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  6. 6. B · O(n log n)
  7. 7. B · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
  8. 8. C · O((V + E) log V)

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