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 žymėjimas nusako apatinį augimo rėžį?

  1. AΩ (didžioji Omega)
  2. Bo (mažasis o)
  3. CO (didysis O)
  4. DΘ (didžioji Teta)
2.Lengvas

Kurią projektavimo strategiją naudoja rikiavimas suliejimu?

  1. ADinaminį programavimą
  2. BSkaldyk ir valdyk
  3. CGodųjį pasirinkimą
  4. DPerrinkimą (brute force)
3.Lengvas

Kaip vadinamas O(2ⁿ) augimas?

  1. ATiesinis
  2. BLogaritminis
  3. CPolinominis
  4. DEksponentinis
4.Vidutinis

Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?

  1. APasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  2. BPirmiausia pasirinkti trumpiausią veiklą
  3. CPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
  4. DPasirinkti anksčiausiai prasidedančią veiklą
5.Vidutinis

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

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

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

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

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

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

Kuris iš šių įvykdomumo uždavinių, kaip žinoma, išsprendžiamas per polinominį laiką?

  1. A3-SAT, kai kiekviename disjunkte yra lygiai trys literalai
  2. BBendrasis SAT konjunkcinės normaliosios formos formulėms
  3. CLoginės schemos įvykdomumas
  4. D2-SAT, kai kiekviename disjunkte yra daugiausia du literalai

Atsakymai

  1. 1. A · Ω (didžioji Omega)
  2. 2. B · Skaldyk ir valdyk
  3. 3. D · Eksponentinis
  4. 4. A · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  5. 5. A · Jis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  6. 6. C · O(log n)
  7. 7. C · Tai NP-sunkus uždavinys
  8. 8. D · 2-SAT, kai kiekviename disjunkte yra daugiausia du literalai

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