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

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

  1. AMažoji omega
  2. BDidžioji Teta
  3. CDidysis O
  4. DDidžioji Omega
2.Lengvas

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

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

Ką reiškia, jei operacija atliekama per O(1) laiką?

  1. AJą galima vykdyti tik vieną kartą
  2. BJi visada trunka lygiai vieną sekundę
  3. CJos vykdymo laikas nedidėja didėjant įvesties dydžiui
  4. DJi apdoroja lygiai vieną elementą per vykdymo sekundę
4.Vidutinis

Koks yra dviejų n × n matricų daugybos standartiniu trigubu ciklu laiko sudėtingumas?

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

Dinaminis programavimas naudingas, kai uždavinys turi:

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

Kuris algoritmas randa trumpiausius kelius iš vienos pradinės viršūnės grafe, kurio briaunų svoriai neneigiami?

  1. AVisais atvejais būtinas Belmano–Fordo algoritmas
  2. BKruskalo algoritmas
  3. CPaieška gilyn (DFS)
  4. DDijkstros algoritmas
7.Sunkus

Kaip Bellmano–Fordo algoritmas aptinka iš šaltinio pasiekiamą neigiamo svorio ciklą?

  1. AJis suskaičiuoja ciklus paieška gilyn
  2. BPo V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
  3. CJis du kartus paleidžia Dijkstros algoritmą ir palygina abu atstumų rezultatus
  4. DJis patikrina, ar kuri nors briauna turi neigiamą svorį
8.Sunkus

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

  1. AAbiem variantams
  2. BTrupmeninei kuprinei, kai daiktus galima dalyti
  3. CNė vienam variantui
  4. D0/1 kuprinei, kai daiktai visada imami ištisi

Atsakymai

  1. 1. C · Didysis O
  2. 2. C · O(2ⁿ)
  3. 3. C · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  4. 4. C · O(n³)
  5. 5. D · Persidengiančius poproblemius ir optimalią postruktūrą
  6. 6. D · Dijkstros algoritmas
  7. 7. B · Po V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
  8. 8. B · Trupmeninei kuprinei, kai daiktus galima dalyti

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