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 tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

Kuris žymėjimas nusako apatinį augimo rėžį?

  1. AΩ (didžioji Omega)
  2. BO (didysis O)
  3. Co (mažasis o)
  4. DΘ (didžioji Teta)
3.Lengvas

Erdvės (atminties) sudėtingumas matuoja:

  1. AProgramos failo užimamą vietą diske jį sukompiliavus
  2. BKiek atminties algoritmui reikia didėjant įvesties duomenims
  3. CKodo eilučių skaičių
  4. DFizinį kompiuterio dydį
4.Vidutinis

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

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

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Koks yra n-tojo Fibonačio skaičiaus skaičiavimo laiko sudėtingumas, naudojant lentelę „iš apačios į viršų“?

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

Kuris P klasės apibrėžimas teisingas?

  1. AUždaviniai, kuriuos galima spręsti lygiagrečiai
  2. BSprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per polinominį laiką
  3. CUždaviniai, kuriems bet kuriame kompiuteryje reikia eksponentinio laiko
  4. DUždaviniai, kurių sprendinius galima patikrinti, bet niekada nerasti per polinominį laiką
8.Sunkus

Taikant pagrindinę teoremą (master theorem), T(n) = 8T(n/2) + O(n²) sprendinys yra:

  1. AΘ(n² log n)
  2. BΘ(n³)
  3. CΘ(n log n)
  4. DΘ(n²)

Atsakymai

  1. 1. A · O(n)
  2. 2. A · Ω (didžioji Omega)
  3. 3. B · Kiek atminties algoritmui reikia didėjant įvesties duomenims
  4. 4. B · Apie log₂ n
  5. 5. A · O(n)
  6. 6. B · O(n)
  7. 7. B · Sprendimo uždaviniai, kuriuos deterministinis algoritmas išsprendžia per polinominį laiką
  8. 8. B · Θ(n³)

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