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

Kiek papildomos atminties naudoja standartinis masyvu grįstas rikiavimas suliejimu?

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

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

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

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

Kiek lygmenų turi rikiavimo suliejimu rekursija n elementų masyvui?

  1. AApie log₂ n
  2. BApie n / 2
  3. CApie √n
  4. DApie n
5.Vidutinis

Rekurentinės lygties T(n) = 2T(n/2) + O(n) sprendinys yra:

  1. AO(n²)
  2. BO(n)
  3. CO(log n)
  4. DO(n log n)
6.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. BUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai
  3. CUždavinį galima išspręsti per pastovų laiką
  4. DVisi daliniai uždaviniai yra vienodo dydžio
7.Sunkus

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

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

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for (j = i; j ≤ n; j = j + i) atlikti O(1) darbą?

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

Atsakymai

  1. 1. C · O(n)
  2. 2. B · O(1)
  3. 3. C · O(n³)
  4. 4. A · Apie log₂ n
  5. 5. D · O(n log n)
  6. 6. A · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  7. 7. C · n = o(n²), bet n nėra o(n)
  8. 8. C · O(n log n)

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