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(E log V)
  3. CO(V²)
  4. DO(V + E)
2.Lengvas

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

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

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

  1. ADidžioji Teta
  2. BMažoji omega
  3. CDidysis O
  4. DDidžioji Omega
4.Vidutinis

Ką reiškia, kad uždavinys turi optimalią struktūrą (optimal substructure)?

  1. AOptimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  2. BVisi daliniai uždaviniai yra vienodo dydžio
  3. CUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai
  4. DUždavinį galima išspręsti per pastovų laiką
5.Vidutinis

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu atsitiktinės tvarkos masyvu
  2. BSu masyvu, kurio visi elementai skirtingi
  3. CSu 2 ilgio masyvu
  4. DSu jau surikiuotu masyvu
6.Vidutinis

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

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

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

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

Kuris NP klasės apibrėžimas teisingas?

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

Atsakymai

  1. 1. D · O(V + E)
  2. 2. D · O(n)
  3. 3. C · Didysis O
  4. 4. A · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  5. 5. D · Su jau surikiuotu masyvu
  6. 6. A · O(2ⁿ)
  7. 7. D · O(1) vienam padidinimui
  8. 8. A · 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.