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

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

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

Algoritmo vykdymo laikas yra O(n). Kaip vadinamas toks augimas?

  1. AKvadratinis
  2. BPastovus
  3. CLogaritminis
  4. DTiesinis
3.Lengvas

Kas yra rekursinės funkcijos bazinis atvejis?

  1. AAtvejis su didžiausia įvestimi, kuris apdorojamas prieš bet kokius rekursinius kvietimus
  2. BAtvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  3. CPirmoji funkcijos eilutė
  4. DKvietimas, naudojantis daugiausia atminties
4.Vidutinis

Naivaus rekursyvaus Fibonačio skaičių skaičiavimo (fib(n) = fib(n−1) + fib(n−2)) laiko sudėtingumas yra:

  1. AEksponentinis
  2. BPastovus
  3. CLogaritminis
  4. DTiesinis
5.Vidutinis

Kodėl didžiojo O žymėjime logaritmo pagrindas paprastai nenurodomas, kaip O(log n)?

  1. APagrindas svarbus tik mažiems n
  2. BSkirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  3. CLogaritmai visada apvalinami iki sveikųjų skaičių
  4. DVisų logaritmų informatikoje pagrindas yra 10, todėl jis numanomas
6.Vidutinis

Dinaminis programavimas naudingas, kai uždavinys turi:

  1. APersidengiančius poproblemius ir optimalią postruktūrą
  2. BVisai jokių poproblemių, todėl jį galima išspręsti vienu žingsniu
  3. CTik atsitiktinius įvesties duomenis
  4. DVieną ciklą
7.Sunkus

Kuris teiginys apie k-ojo mažiausio nesurikiuoto masyvo elemento išrinkimą teisingas?

  1. AQuickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju
  2. BQuickselect blogiausiu atveju veikia per O(log n), nes rekursija vyksta tik į vieną atramos elemento pusę
  3. CIšrinkimas įmanomas tik per O(n²)
  4. DIšrinkimui visada reikia Ω(n log n), nes reikia rikiavimo
8.Sunkus

Uždavinys yra NP-pilnas, jei jis:

  1. ANeišsprendžiamas
  2. BIšsprendžiamas per polinominį laiką
  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. D · O(log n)
  2. 2. D · Tiesinis
  3. 3. B · Atvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  4. 4. A · Eksponentinis
  5. 5. B · Skirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  6. 6. A · Persidengiančius poproblemius ir optimalią postruktūrą
  7. 7. A · Quickselect veikia per tikėtiną O(n), o medianų medianos metodas garantuoja O(n) blogiausiu atveju
  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.