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

Koks yra paieškos gilyn laiko sudėtingumas grafui, saugomam gretimumo sąrašais?

  1. AO(V + E)
  2. BO(V × E)
  3. CO(E log V)
  4. DO(V²)
2.Lengvas

Kuris iš šių vykdymo laikų yra polinominis?

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

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

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

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

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

  1. ARikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
  2. BRikiavimas įterpimu blogiausiu atveju yra O(n log n)
  3. CRekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų
  4. DRikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
6.Vidutinis

Kuris rikiavimo algoritmas yra stabilus?

  1. ARikiavimas suliejimu
  2. BGreitasis rikiavimas (įprasta versija vietoje)
  3. CRikiavimas krūva
  4. DRikiavimas išrinkimu (įprasta versija)
7.Sunkus

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

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

Kuris NP klasės apibrėžimas teisingas?

  1. AUždaviniai, kurių negalima išspręsti per polinominį laiką
  2. BSprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
  3. CUždaviniai, kurie nėra polinominiai
  4. DUždaviniai, kurių neišsprendžia joks algoritmas

Atsakymai

  1. 1. A · O(V + E)
  2. 2. A · O(n³)
  3. 3. A · O(1)
  4. 4. B · O(n)
  5. 5. D · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  6. 6. A · Rikiavimas suliejimu
  7. 7. A · n = o(n²), bet n nėra o(n)
  8. 8. B · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką

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