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

Erdvės (atminties) sudėtingumas matuoja:

  1. AKodo eilučių skaičių
  2. BProgramos failo užimamą vietą diske jį sukompiliavus
  3. CKiek atminties algoritmui reikia didėjant įvesties duomenims
  4. DFizinį kompiuterio dydį
2.Lengvas

Koks yra dvejetainės paieškos surikiuotame masyve laiko sudėtingumas?

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

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

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

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Koks yra standartinio dinaminio programavimo algoritmo, ieškančio m ir n ilgio eilučių ilgiausio bendro posekio, laiko sudėtingumas?

  1. AO(m + n)
  2. BO(mn)
  3. CO(2m+n)
  4. DO(mn log n)
6.Vidutinis

Vieną kartą surikiuojate n elementų masyvą, o tada dvejetaine paieška atsakote į k priklausomybės užklausų. Kokia bendra kaina?

  1. AO(k n log n)
  2. BO(n + k)
  3. CO(n log n + k log n)
  4. DO(nk)
7.Sunkus

Ką reikia padaryti, norint parodyti, kad naujas uždavinys X yra NP-sunkus?

  1. APer polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X
  2. BParodyti, kad X neturi polinominio algoritmo mažoms įvestims
  3. CParodyti, kad X galima patikrinti per polinominį laiką
  4. DPer polinominį laiką redukuoti X į žinomą NP-sunkų uždavinį
8.Sunkus

Kuris P klasės apibrėžimas teisingas?

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

Atsakymai

  1. 1. C · Kiek atminties algoritmui reikia didėjant įvesties duomenims
  2. 2. C · O(log n)
  3. 3. A · O(log n)
  4. 4. D · O(n)
  5. 5. B · O(mn)
  6. 6. C · O(n log n + k log n)
  7. 7. A · Per polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X
  8. 8. D · 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.