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

Kiek papildomos atminties naudoja standartinis masyvu grįstas rikiavimas suliejimu?

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

Koks yra 3n² + 5n + 2 didysis O?

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

Koks yra paieškos gilyn laiko sudėtingumas grafui, saugomam gretimumo sąrašais?

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

Kaip Primo algoritmas sudaro minimalų jungiamąjį medį?

  1. AJis šalina brangiausią briauną, kol nebelieka ciklų
  2. BJis vykdo paiešką platyn ir pasilieka BFS medį
  3. CJis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  4. DJis surikiuoja visas briaunas pagal svorį ir prideda kiekvieną, jei ji miške nesudaro ciklo
5.Vidutinis

Kiek steko vietos naudoja paprasta rekursinė faktorialo funkcija fact(n) = n × fact(n − 1)?

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

Ką reiškia, kad uždavinys turi optimalią struktūrą (optimal substructure)?

  1. AVisi daliniai uždaviniai yra vienodo dydžio
  2. BUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai
  3. CUždavinį galima išspręsti per pastovų laiką
  4. DOptimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
7.Sunkus

Kuris NP klasės apibrėžimas teisingas?

  1. AUždaviniai, kurių neišsprendžia joks algoritmas
  2. BSprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
  3. CUždaviniai, kurie nėra polinominiai
  4. DUždaviniai, kurių negalima išspręsti per polinominį laiką
8.Sunkus

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

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

Atsakymai

  1. 1. C · O(n)
  2. 2. C · O(n²)
  3. 3. C · O(V + E)
  4. 4. C · Jis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  5. 5. A · O(n)
  6. 6. D · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  7. 7. B · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
  8. 8. D · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki

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