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

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

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

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

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

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

  1. ATiesinis
  2. BKvadratinis
  3. CPastovus
  4. DLogaritminis
4.Vidutinis

Kiek lygmenų turi rikiavimo suliejimu rekursija n elementų masyvui?

  1. AApie n / 2
  2. BApie n
  3. CApie √n
  4. DApie log₂ n
5.Vidutinis

Koks yra LSD pozicinio rikiavimo (radix sort) vykdymo laikas n sveikųjų skaičių, turinčių d skaitmenų k pagrindo sistemoje?

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

Kam lygus rekurentinės lygties T(n) = 2T(n − 1) + O(1) sprendinys?

  1. AO(n²)
  2. BO(n log n)
  3. CO(2ⁿ)
  4. DO(n)
7.Sunkus

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

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

Trumpiausius paprastuosius kelius galima rasti per polinominį laiką. Kas žinoma apie ilgiausio paprastojo kelio tarp dviejų viršūnių paiešką bendrajame grafe?

  1. ATai NP-sunkus uždavinys
  2. BJį galima išspręsti Dijkstros algoritmu su priešingo ženklo svoriais
  3. CJis visada išsprendžiamas per O(V + E)
  4. DJis neišsprendžiamas

Atsakymai

  1. 1. C · O(n + k)
  2. 2. B · O(V + E)
  3. 3. A · Tiesinis
  4. 4. D · Apie log₂ n
  5. 5. C · O(d(n + k))
  6. 6. C · O(2ⁿ)
  7. 7. D · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
  8. 8. A · Tai NP-sunkus uždavinys

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