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 rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

Kaip vadinamas O(2ⁿ) augimas?

  1. ALogaritminis
  2. BTiesinis
  3. CPolinominis
  4. DEksponentinis
3.Lengvas

Kas yra rekursija?

  1. AFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  2. BCiklas, kuris niekada nesibaigia
  3. CDuomenų struktūros tipas
  4. DRikiavimo metodas
4.Vidutinis

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

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

Kuris rikiavimo algoritmas yra stabilus?

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

Koks yra dviejų n × n matricų daugybos standartiniu trigubu ciklu laiko sudėtingumas?

  1. AO(n² log n)
  2. BO(n²)
  3. CO(n³)
  4. DO(n)
7.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)
8.Sunkus

Ar 22n priklauso O(2ⁿ)?

  1. ANe, nes 22n auga lėčiau už 2ⁿ
  2. BTaip, nes abu yra eksponentiniai
  3. CTaip, nes didžiajame O pastovūs laipsnio rodiklio daugikliai visada nepaisomi
  4. DNe, nes 22n = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai

Atsakymai

  1. 1. A · O(n)
  2. 2. D · Eksponentinis
  3. 3. A · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. 4. D · O(n²)
  5. 5. C · Rikiavimas suliejimu
  6. 6. C · O(n³)
  7. 7. C · O(n log n)
  8. 8. D · Ne, nes 22n = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai

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