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

O(n²) algoritmas, kai n = 1000, trunka 1 sekundę. Maždaug kiek jis truks, kai n = 2000?

  1. A1 sekundę
  2. B4 sekundes
  3. C8 sekundes
  4. D2 sekundes
3.Lengvas

Kuri sudėtingumo klasė auga greičiausiai, kai n didelis?

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

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

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

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

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

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

  1. AJis šalina brangiausią briauną, kol nebelieka ciklų
  2. BJis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  3. CJis surikiuoja visas briaunas pagal svorį ir prideda kiekvieną, jei ji miške nesudaro ciklo
  4. DJis vykdo paiešką platyn ir pasilieka BFS medį
7.Sunkus

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

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

Kuriam kuprinės uždavinio variantui godžioji taisyklė „imti daiktus pagal vertės ir svorio santykį“ visada duoda optimalų atsakymą?

  1. A0/1 kuprinei, kai daiktai visada imami ištisi
  2. BAbiem variantams
  3. CTrupmeninei kuprinei, kai daiktus galima dalyti
  4. DNė vienam variantui

Atsakymai

  1. 1. A · Jis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  2. 2. B · 4 sekundes
  3. 3. A · O(2ⁿ)
  4. 4. C · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  5. 5. D · O(n)
  6. 6. B · Jis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
  7. 7. A · Atraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį
  8. 8. C · Trupmeninei kuprinei, kai daiktus galima dalyti

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