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

Algoritmo vykdymo laikas yra O(n). Kaip vadinamas toks augimas?

  1. ATiesinis
  2. BKvadratinis
  3. CLogaritminis
  4. DPastovus
2.Lengvas

Kaip vadinamas O(2ⁿ) augimas?

  1. ALogaritminis
  2. BPolinominis
  3. CEksponentinis
  4. DTiesinis
3.Lengvas

Erdvės (atminties) sudėtingumas matuoja:

  1. AKiek atminties algoritmui reikia didėjant įvesties duomenims
  2. BKodo eilučių skaičių
  3. CFizinį kompiuterio dydį
  4. DProgramos failo užimamą vietą diske jį sukompiliavus
4.Vidutinis

Funkcija vykdo vieną n iteracijų ciklą, o paskui, atskirai, dar vieną n iteracijų ciklą. Koks jos laiko sudėtingumas?

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

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

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

Ar teisinga sakyti, kad O(n²) algoritmas yra ir O(n³)?

  1. ANe, nes dideliems n n³ mažesnis už n²
  2. BTaip, bet tik jei n mažesnis už 100
  3. CNe, nes didysis O visada turi nurodyti tikslų funkcijos augimo greitį
  4. DTaip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
7.Sunkus

Kaip dideliems n palyginami n! ir 2ⁿ?

  1. An! auga greičiau už 2ⁿ
  2. Bn! yra O(n²)
  3. CJie auga vienodu greičiu
  4. D2ⁿ auga greičiau už n!
8.Sunkus

Kuris algoritmas randa minimalų jungiamąjį medį, pakartotinai pridėdamas pigiausią briauną, kuri nesudaro ciklo?

  1. APrimo algoritmas, pradedant nuo vienos viršūnės
  2. BKruskalo algoritmas
  3. CFloido–Voršalo algoritmas
  4. DDijkstros algoritmas

Atsakymai

  1. 1. A · Tiesinis
  2. 2. C · Eksponentinis
  3. 3. A · Kiek atminties algoritmui reikia didėjant įvesties duomenims
  4. 4. A · O(n)
  5. 5. A · O(n log n)
  6. 6. D · Taip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  7. 7. A · n! auga greičiau už 2ⁿ
  8. 8. B · Kruskalo algoritmas

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