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

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

Kuris iš šių auga lėčiausiai, kai n tampa didelis?

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

Kaip vadinamas O(2ⁿ) augimas?

  1. APolinominis
  2. BLogaritminis
  3. CTiesinis
  4. DEksponentinis
4.Vidutinis

Koks yra LSD pozicinio rikiavimo (radix sort) vykdymo laikas n sveikųjų skaičių, turinčių d skaitmenų k pagrindo sistemoje?

  1. AO(n log n)
  2. BO(d(n + k))
  3. CO(n²)
  4. DO(dn log k)
5.Vidutinis

Palyginimais pagrįsto rikiavimo apatinis rėžis blogiausiu atveju yra:

  1. AΩ(log n)
  2. BΩ(n)
  3. CΩ(n log n)
  4. DΩ(n²)
6.Vidutinis

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

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

Ar 22n priklauso O(2ⁿ)?

  1. ATaip, nes didžiajame O pastovūs laipsnio rodiklio daugikliai visada nepaisomi
  2. BNe, nes 22n = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai
  3. CNe, nes 22n auga lėčiau už 2ⁿ
  4. DTaip, nes abu yra eksponentiniai
8.Sunkus

Kuris teiginys apie P ir NP yra teisingas?

  1. AKiekvienas P klasės uždavinys taip pat priklauso NP
  2. BNP reiškia „nepolinominis“ (not polynomial)
  3. CNP uždavinių sprendinių negalima greitai patikrinti
  4. DĮrodyta, kad P ≠ NP

Atsakymai

  1. 1. A · O(1)
  2. 2. D · O(log n)
  3. 3. D · Eksponentinis
  4. 4. B · O(d(n + k))
  5. 5. C · Ω(n log n)
  6. 6. C · O(n log n)
  7. 7. B · Ne, nes 22n = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai
  8. 8. A · Kiekvienas P klasės uždavinys taip pat priklauso NP

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