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 = 1 milijonas, trunka 3 sekundes. Maždaug kiek jis truks, kai n = 2 milijonai?

  1. A9 sekundes
  2. B3 sekundes
  3. C12 sekundžių
  4. D6 sekundes
2.Lengvas

Koks yra rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

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

Kam lygus log₂ 1024?

  1. A32
  2. B512
  3. C10
  4. D12
4.Vidutinis

Koks yra n-tojo Fibonačio skaičiaus skaičiavimo laiko sudėtingumas, naudojant lentelę „iš apačios į viršų“?

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

Funkcija vykdo vieną n iteracijų ciklą, o paskui, atskirai, dar vieną n iteracijų ciklą. Koks jos laiko sudėtingumas?

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

Turint 1, 3 ir 4 vertės monetas ir 6 sumą, kiek monetų panaudoja godusis metodas „pirmiausia didžiausia moneta“, palyginti su optimaliu sprendiniu?

  1. AGodusis panaudoja 3 monetas; optimalus sprendinys – 2
  2. BGodusis panaudoja 4 monetas; optimalus sprendinys – 3
  3. CGodusis panaudoja 2 monetas; optimalus sprendinys – 2
  4. DGodusis panaudoja 3 monetas; optimalus sprendinys – 3
7.Sunkus

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

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

Kuris P klasės apibrėžimas teisingas?

  1. AUždaviniai, kurių sprendinius galima patikrinti, bet niekada nerasti per polinominį laiką
  2. BSprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per polinominį laiką
  3. CUždaviniai, kuriuos galima spręsti lygiagrečiai
  4. DUždaviniai, kuriems bet kuriame kompiuteryje reikia eksponentinio laiko

Atsakymai

  1. 1. D · 6 sekundes
  2. 2. C · O(n log n)
  3. 3. C · 10
  4. 4. C · O(n)
  5. 5. A · O(n)
  6. 6. A · Godusis panaudoja 3 monetas; optimalus sprendinys – 2
  7. 7. A · O((V + E) log V)
  8. 8. B · Sprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per polinominį laiką

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