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

Kurią projektavimo strategiją naudoja rikiavimas suliejimu?

  1. ASkaldyk ir valdyk
  2. BPerrinkimą (brute force)
  3. CGodųjį pasirinkimą
  4. DDinaminį programavimą
2.Lengvas

Koks yra rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

Koks yra didžiausios reikšmės paieškos nesurikiuotame n skaičių masyve laiko sudėtingumas?

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

Godusis algoritmas:

  1. AIšbando kiekvieną galimą sprendinį
  2. BVisada pateikia optimalų sprendinį
  3. CKiekviename žingsnyje priima lokaliai geriausią sprendimą
  4. DNaudoja tik rekursiją
5.Vidutinis

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

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

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu jau surikiuotu masyvu
  2. BSu atsitiktinės tvarkos masyvu
  3. CSu 2 ilgio masyvu
  4. DSu masyvu, kurio visi elementai skirtingi
7.Sunkus

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

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

Kas išplauktų, jei kas nors rastų polinominio laiko algoritmą vienam NP-pilnam uždaviniui?

  1. AVisi eksponentinio laiko algoritmai nedelsiant imtų veikti tiesiniu laiku
  2. BStabdymo problema taptų išsprendžiama
  3. CTik tas vienas uždavinys pereitų į P
  4. DKiekvieną NP uždavinį būtų galima išspręsti per polinominį laiką, taigi P = NP

Atsakymai

  1. 1. A · Skaldyk ir valdyk
  2. 2. D · O(n)
  3. 3. D · O(n)
  4. 4. C · Kiekviename žingsnyje priima lokaliai geriausią sprendimą
  5. 5. D · Apie log₂ n
  6. 6. A · Su jau surikiuotu masyvu
  7. 7. B · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
  8. 8. D · Kiekvieną NP uždavinį būtų galima išspręsti per polinominį laiką, taigi P = NP

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