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 iš šių vykdymo laikų yra polinominis?

  1. AO(n!)
  2. BO(n³)
  3. CO(nⁿ)
  4. DO(2ⁿ)
2.Lengvas

Kaip veikia rikiavimas išrinkimu?

  1. AJis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  2. BJis kiekvieną elementą postūmiais įterpia į augančią surikiuotą dalį
  3. CJis padalija masyvą pusiau ir sulieja puses
  4. DJis pakartotinai sukeičia neteisinga tvarka esančius gretimus elementus
3.Lengvas

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

Kodėl dinaminis programavimas realiai nepagreitina rikiavimo suliejimu?

  1. AJo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  2. BRikiavimas suliejimu neturi rekursinės struktūros
  3. CRikiavimas suliejimu jau yra O(n)
  4. DDinaminis programavimas veikia tik su grafų uždaviniais, bet ne su masyvais
5.Vidutinis

Godusis algoritmas:

  1. AIšbando kiekvieną galimą sprendinį
  2. BKiekviename žingsnyje priima lokaliai geriausią sprendimą
  3. CNaudoja tik rekursiją
  4. DVisada pateikia optimalų sprendinį
6.Vidutinis

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

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

Ką nustatė Cooko–Levino teorema?

  1. AStabdymo problema yra neišsprendžiama
  2. BLoginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  3. CP nelygu NP
  4. DKiekvieną NP uždavinį galima išspręsti per eksponentinį laiką
8.Sunkus

Strasseno algoritmas matricas daugina naudodamas 7, o ne 8 rekursines pusės dydžio blokų daugybas. Koks jo vykdymo laikas?

  1. AΘ(n² log n)
  2. BΘ(n2)
  3. CΘ(nlog₂ 7), apie n2,81
  4. DΘ(n³)

Atsakymai

  1. 1. B · O(n³)
  2. 2. A · Jis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  3. 3. B · O(1)
  4. 4. A · Jo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti
  5. 5. B · Kiekviename žingsnyje priima lokaliai geriausią sprendimą
  6. 6. D · O(n²)
  7. 7. B · Loginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  8. 8. C · Θ(nlog₂ 7), apie n2,81

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