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. APerrinkimą (brute force)
  2. BDinaminį programavimą
  3. CSkaldyk ir valdyk
  4. DGodųjį pasirinkimą
2.Lengvas

Kuris rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

  1. ARikiavimas suliejimu
  2. BGreitasis rikiavimas (quicksort)
  3. CRikiavimas įterpimu
  4. DBurbuliuko rikiavimas
3.Lengvas

Kas yra memoizacija?

  1. AFunkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
  2. BKomentarų rašymas prie kiekvienos kodo eilutės
  3. CAtminties atlaisvinimas funkcijai grįžus
  4. DAutomatinis rekursijos pavertimas ekvivalenčiu ciklu, kad nebereikėtų kvietimų steko
4.Vidutinis

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

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

Kuris algoritmas randa trumpiausius kelius iš vienos pradinės viršūnės grafe, kurio briaunų svoriai neneigiami?

  1. APaieška gilyn (DFS)
  2. BKruskalo algoritmas
  3. CVisais atvejais būtinas Belmano–Fordo algoritmas
  4. DDijkstros algoritmas
6.Vidutinis

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

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

Topologinis rikiavimas galimas tik:

  1. APilniesiems grafams
  2. BKryptiniams acikliniams grafams
  3. CGrafams su neigiamais svoriais
  4. DNekryptiniams grafams
8.Sunkus

Kodėl bet kuriai palyginimais pagrįstai paieškai surikiuotame masyve blogiausiu atveju reikia Ω(log n) palyginimų?

  1. AKiekvienas palyginimas trunka logaritminį laiką
  2. BSprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
  3. CKiekvieną elementą reikia palyginti bent kartą
  4. DDvejetainė paieška yra vienintelis galimas algoritmas, ir jam reikia log₂ n palyginimų

Atsakymai

  1. 1. C · Skaldyk ir valdyk
  2. 2. B · Greitasis rikiavimas (quicksort)
  3. 3. A · Funkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
  4. 4. B · O(V × E)
  5. 5. D · Dijkstros algoritmas
  6. 6. C · O(2ⁿ)
  7. 7. B · Kryptiniams acikliniams grafams
  8. 8. B · Sprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n

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