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ų auga lėčiausiai, kai n tampa didelis?

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

Kurią projektavimo strategiją naudoja rikiavimas suliejimu?

  1. APerrinkimą (brute force)
  2. BDinaminį programavimą
  3. CSkaldyk ir valdyk
  4. DGodųjį pasirinkimą
3.Lengvas

Ką apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ADidžiausią laiką tarp visų n dydžio įvesčių
  2. BLaiką su mažiausia įvestimi
  3. CLaiką lėtame kompiuteryje
  4. DTikėtiną laiką su atsitiktine n dydžio įvestimi
4.Vidutinis

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

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

Koks yra amortizuotas laiko sudėtingumas pridedant elementą į dinaminio masyvo, kuris prisipildęs padvigubina savo talpą, galą?

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

Ką apskaičiuoja Floydo–Warshallo algoritmas ir kaip greitai?

  1. ATrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)
  2. BTopologinę tvarką per O(V²)
  3. CTrumpiausius kelius tarp visų viršūnių porų per O(V³)
  4. DMinimalų jungiamąjį medį per O(E log V)
7.Sunkus

Kuris teiginys apie mažojo o žymėjimą teisingas?

  1. An = o(n), nes kiekviena funkcija yra mažasis o pati sau
  2. B2n = o(n), nes 2n auga lėtai
  3. Cn² = o(n)
  4. Dn = o(n²), bet n nėra o(n)
8.Sunkus

Kodėl Dijkstros algoritmas gali duoti neteisingus rezultatus, kai kai kurie briaunų svoriai neigiami?

  1. AJis veikia tik su nekryptiniais grafais
  2. BTies kiekviena neigiama briauna jis patenka į begalinį ciklą
  3. CNeigiamų skaičių negalima saugoti prioritetinėje eilėje
  4. DViršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią

Atsakymai

  1. 1. B · O(log n)
  2. 2. C · Skaldyk ir valdyk
  3. 3. A · Didžiausią laiką tarp visų n dydžio įvesčių
  4. 4. A · Apie log₂ n
  5. 5. C · O(1)
  6. 6. C · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  7. 7. D · n = o(n²), bet n nėra o(n)
  8. 8. D · Viršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią

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