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(2ⁿ)
  4. DO(n!)
2.Lengvas

Ką apibūdina algoritmo vykdymo laikas blogiausiu atveju?

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

Kuri sudėtingumo klasė auga greičiausiai, kai n didelis?

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

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

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

Koks yra Bellmano–Fordo algoritmo laiko sudėtingumas grafui su V viršūnių ir E briaunų?

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V³ × E)
  4. DO(V + E)
6.Vidutinis

Ką matuoja amortizuotoji analizė?

  1. AVidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
  2. BAlgoritmo kainą su geriausia įvestimi
  3. CTikėtiną kainą su atsitiktinėmis įvestimis
  4. DVienos brangiausios operacijos bet kurioje sekos vietoje kainą
7.Sunkus

Karacubos daugyba tenkina T(n) = 3T(n/2) + O(n). Kam lygus sprendinys?

  1. AΘ(n log n)
  2. BΘ(nlog₂ 3), apie n1,585
  3. CΘ(n²)
  4. DΘ(n3)
8.Sunkus

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

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

Atsakymai

  1. 1. A · O(n³)
  2. 2. A · Didžiausią laiką tarp visų n dydžio įvesčių
  3. 3. C · O(2ⁿ)
  4. 4. D · Jis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  5. 5. B · O(V × E)
  6. 6. A · Vidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
  7. 7. B · Θ(nlog₂ 3), apie n1,585
  8. 8. D · n = o(n²), bet n nėra o(n)

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