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 rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

  1. ARikiavimas suliejimu
  2. BRikiavimas įterpimu
  3. CBurbuliuko rikiavimas
  4. DGreitasis rikiavimas (quicksort)
2.Lengvas

Koks yra tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

O(n²) algoritmas, kai n = 1000, trunka 1 sekundę. Maždaug kiek jis truks, kai n = 2000?

  1. A8 sekundes
  2. B1 sekundę
  3. C4 sekundes
  4. D2 sekundes
4.Vidutinis

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

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

Paieška platyn nesvoriniame grafe randa:

  1. AMinimalų jungiamąjį medį
  2. BTopologinę tvarką bet kuriame grafe
  3. CTrumpiausius kelius grafuose, turinčiuose neigiamų briaunų svorių
  4. DTrumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
6.Vidutinis

Koks yra greitojo rikiavimo (quicksort) laiko sudėtingumas blogiausiu atveju?

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

Kokia amortizuotoji dvejetainio skaitiklio padidinimo kaina, žinant, kad vienas padidinimas gali pakeisti daug bitų?

  1. AO(n) vienam padidinimui
  2. BO(log n) vienam padidinimui
  3. CO(n log n) vienam padidinimui
  4. DO(1) vienam padidinimui
8.Sunkus

Kuris iš šių įvykdomumo uždavinių, kaip žinoma, išsprendžiamas per polinominį laiką?

  1. ABendrasis SAT konjunkcinės normaliosios formos formulėms
  2. BLoginės schemos įvykdomumas
  3. C3-SAT, kai kiekviename disjunkte yra lygiai trys literalai
  4. D2-SAT, kai kiekviename disjunkte yra daugiausia du literalai

Atsakymai

  1. 1. D · Greitasis rikiavimas (quicksort)
  2. 2. A · O(n)
  3. 3. C · 4 sekundes
  4. 4. B · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  5. 5. D · Trumpiausius kelius (pagal briaunų skaičių) nuo pradinės viršūnės
  6. 6. C · O(n²)
  7. 7. D · O(1) vienam padidinimui
  8. 8. D · 2-SAT, kai kiekviename disjunkte yra daugiausia du literalai

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