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 suliejimu laiko sudėtingumas blogiausiu atveju?

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

Kam lygus log₂ 1024?

  1. A10
  2. B32
  3. C12
  4. D512
3.Lengvas

Koks yra rikiavimo įterpimu laiko sudėtingumas blogiausiu atveju?

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

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Ką reiškia, kad uždavinys turi optimalią struktūrą (optimal substructure)?

  1. AVisi daliniai uždaviniai yra vienodo dydžio
  2. BUždavinį galima išspręsti per pastovų laiką
  3. COptimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  4. DUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai
6.Vidutinis

Kaip Primo algoritmas sudaro minimalų jungiamąjį medį?

  1. AJis vykdo paiešką platyn ir pasilieka BFS medį
  2. BJis surikiuoja visas briaunas pagal svorį ir prideda kiekvieną, jei ji miške nesudaro ciklo
  3. CJis šalina brangiausią briauną, kol nebelieka ciklų
  4. DJis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
7.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žiami uždaviniai priklauso NP, o praktiškai neišsprendžiami – P
  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
8.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. BVisada pirmojo elemento parinkimas
  3. CAtraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį
  4. DRekursijos taikymas tik kairiajai pusei

Atsakymai

  1. 1. C · O(n log n)
  2. 2. A · 10
  3. 3. C · O(n²)
  4. 4. A · O(n log n)
  5. 5. C · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  6. 6. D · Jis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  7. 7. 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
  8. 8. C · Atraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį

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