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 f(n) = Θ(g(n))?

  1. Af auga griežtai greičiau už g
  2. Bf auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  3. Cf visada mažesnė už g su kiekvienu n, todėl g riboja ją iš viršaus, bet niekada iš apačios
  4. Df auga griežtai lėčiau už g
2.Lengvas

Kas yra perrinkimo (brute force) algoritmas?

  1. AAlgoritmas, išbandantis visus galimus kandidatinius sprendinius
  2. BAlgoritmas, kuris visada naudoja rekursiją
  3. CAlgoritmas, veikiantis daugelyje procesorių
  4. DAlgoritmas, atsitiktinai spėjantis atsakymą
3.Lengvas

Koks yra rikiavimo skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

Kodėl dinaminis programavimas realiai nepagreitina rikiavimo suliejimu?

  1. AJo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  2. BDinaminis programavimas veikia tik su grafų uždaviniais, bet ne su masyvais
  3. CRikiavimas suliejimu jau yra O(n)
  4. DRikiavimas suliejimu neturi rekursinės struktūros
5.Vidutinis

Kuris teiginys apie rekursinę funkciją be pasiekiamo bazinio atvejo teisingas?

  1. AJi veikia per O(1) laiką
  2. BJi vis kviečia save, kol perpildomas kvietimų stekas
  3. CKompiliatorius visada ją paverčia ciklu, kuris saugiai pasibaigia
  4. DJi automatiškai grąžina 0
6.Vidutinis

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

  1. APirmiausia pasirinkti trumpiausią veiklą
  2. BPasirinkti anksčiausiai prasidedančią veiklą
  3. CPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
  4. DPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
7.Sunkus

Kodėl vidutiniškai paieška maišos lentelėje yra O(1), o blogiausiu atveju – O(n)?

  1. ADaug raktų gali susidurti ir patekti į tą patį krepšelį
  2. BPrieiga prie masyvų yra O(n)
  3. CMaišos funkcijos yra lėtos
  4. DRaktai pirmiausia turi būti surikiuoti
8.Sunkus

Uždavinys yra NP-pilnas, jei jis:

  1. AIšsprendžiamas per polinominį laiką
  2. BNeišsprendžiamas
  3. CNepriklauso NP, bet yra sunkesnis už visus NP uždavinius, pvz., sustojimo problema
  4. DPriklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką

Atsakymai

  1. 1. B · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  2. 2. A · Algoritmas, išbandantis visus galimus kandidatinius sprendinius
  3. 3. A · O(n + k)
  4. 4. A · Jo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  5. 5. B · Ji vis kviečia save, kol perpildomas kvietimų stekas
  6. 6. D · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  7. 7. A · Daug raktų gali susidurti ir patekti į tą patį krepšelį
  8. 8. D · Priklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką

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