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

Kaip veikia rikiavimas išrinkimu?

  1. AJis pakartotinai sukeičia neteisinga tvarka esančius gretimus elementus
  2. BJis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  3. CJis padalija masyvą pusiau ir sulieja puses
  4. DJis kiekvieną elementą postūmiais įterpia į augančią surikiuotą dalį
2.Lengvas

Koks yra tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

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

  1. AΩ (didžioji Omega)
  2. BO (didysis O)
  3. CΘ (didžioji Teta)
  4. Do (mažasis o)
4.Vidutinis

Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?

  1. APasirinkti anksčiausiai prasidedančią veiklą
  2. BPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  3. CPirmiausia pasirinkti trumpiausią veiklą
  4. DPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
5.Vidutinis

Vieną kartą surikiuojate n elementų masyvą, o tada dvejetaine paieška atsakote į k priklausomybės užklausų. Kokia bendra kaina?

  1. AO(n log n + k log n)
  2. BO(n + k)
  3. CO(k n log n)
  4. DO(nk)
6.Vidutinis

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

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

Kokios yra n-tojo Fibonačio skaičiaus skaičiavimo ciklu, saugančiu tik dvi paskutines reikšmes, laiko ir atminties sąnaudos?

  1. AO(2ⁿ) laiko ir O(1) atminties
  2. BO(log n) laiko ir O(n) atminties
  3. CO(n) laiko ir O(n) atminties
  4. DO(n) laiko ir O(1) atminties
8.Sunkus

Kuo skiriasi neišsprendžiamas uždavinys nuo praktiškai neišsprendžiamo (intractable)?

  1. APraktiškai neišsprendžiamų uždavinių negali išspręsti joks algoritmas, o neišsprendžiamiems reikia tik eksponentinio laiko
  2. BNeišsprendžiamo uždavinio visoms įvestims neišsprendžia joks algoritmas, o praktiškai neišsprendžiamas yra išsprendžiamas, bet reikalauja per daug laiko
  3. CNeišsprendžiami uždaviniai priklauso NP, o praktiškai neišsprendžiami – P
  4. DAbu reiškia, kad uždavinys visai neturi algoritmo

Atsakymai

  1. 1. B · Jis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  2. 2. C · O(n)
  3. 3. A · Ω (didžioji Omega)
  4. 4. B · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  5. 5. A · O(n log n + k log n)
  6. 6. C · O(n)
  7. 7. D · O(n) laiko ir O(1) atminties
  8. 8. B · Neišsprendžiamo uždavinio visoms įvestims neišsprendžia joks algoritmas, o praktiškai neišsprendžiamas yra išsprendžiamas, bet reikalauja per daug laiko

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