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 skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

Ką apibūdina vykdymo laikas vidutiniu atveju?

  1. AVidurinę reikšmę tarp geriausio ir blogiausio atvejo vykdymo laikų
  2. BTikėtiną laiką esant tam tikram n dydžio įvesčių skirstiniui
  3. CLaiką labiausiai paplitusiame kompiuteryje
  4. DLaiką vidutinio ilgio įvesčiai
3.Lengvas

Koks yra rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

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

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

Dinaminis programavimas naudingas, kai uždavinys turi:

  1. AVisai jokių poproblemių, todėl jį galima išspręsti vienu žingsniu
  2. BTik atsitiktinius įvesties duomenis
  3. CPersidengiančius poproblemius ir optimalią postruktūrą
  4. DVieną ciklą
6.Vidutinis

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

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

Kuris metodas užtikrina tikėtiną O(n log n) greitojo rikiavimo vykdymo laiką bet kokiems įvesties duomenims?

  1. AĮvesties duomenų surikiavimas prieš paleidžiant greitąjį rikiavimą
  2. BAtraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį
  3. CRekursijos taikymas tik kairiajai pusei
  4. DVisada pirmojo elemento parinkimas
8.Sunkus

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

  1. ANeišsprendžiami uždaviniai priklauso NP, o praktiškai neišsprendžiami – P
  2. BPraktiškai neišsprendžiamų uždavinių negali išspręsti joks algoritmas, o neišsprendžiamiems reikia tik eksponentinio laiko
  3. CAbu reiškia, kad uždavinys visai neturi algoritmo
  4. DNeiš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

Atsakymai

  1. 1. D · O(n + k)
  2. 2. B · Tikėtiną laiką esant tam tikram n dydžio įvesčių skirstiniui
  3. 3. A · O(n)
  4. 4. C · Ω(n log n)
  5. 5. C · Persidengiančius poproblemius ir optimalią postruktūrą
  6. 6. B · O(log n)
  7. 7. B · Atraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį
  8. 8. D · 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.