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

Kas yra rekursinės funkcijos bazinis atvejis?

  1. AAtvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  2. BPirmoji funkcijos eilutė
  3. CKvietimas, naudojantis daugiausia atminties
  4. DAtvejis su didžiausia įvestimi, kuris apdorojamas prieš bet kokius rekursinius kvietimus
3.Lengvas

Ką apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ALaiką su mažiausia įvestimi
  2. BDidžiausią laiką tarp visų n dydžio įvesčių
  3. CLaiką lėtame kompiuteryje
  4. DTikėtiną laiką su atsitiktine n dydžio įvestimi
4.Vidutinis

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu atsitiktinės tvarkos masyvu
  2. BSu masyvu, kurio visi elementai skirtingi
  3. CSu jau surikiuotu masyvu
  4. DSu 2 ilgio masyvu
5.Vidutinis

Koks yra n-tojo Fibonačio skaičiaus skaičiavimo laiko sudėtingumas, naudojant lentelę „iš apačios į viršų“?

  1. AO(log n)
  2. BO(2ⁿ)
  3. CO(n)
  4. DO(n²)
6.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(n²)
  3. CO(n)
  4. DO(log n)
7.Sunkus

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

  1. AJis priklauso P, nes jį išsprendžia Dijkstros algoritmas aplankydamas kiekvieną miestą vieną kartą
  2. BSprendimo versija priklauso P, bet optimizavimo versija yra NP-pilna
  3. CJis neišsprendžiamas
  4. DSprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
8.Sunkus

Topologinis rikiavimas galimas tik:

  1. AKryptiniams acikliniams grafams
  2. BGrafams su neigiamais svoriais
  3. CPilniesiems grafams
  4. DNekryptiniams grafams

Atsakymai

  1. 1. D · Jis pakartotinai randa nesurikiuotos dalies minimumą ir sukeičia jį į priekį
  2. 2. A · Atvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
  3. 3. B · Didžiausią laiką tarp visų n dydžio įvesčių
  4. 4. C · Su jau surikiuotu masyvu
  5. 5. C · O(n)
  6. 6. A · O(n log n)
  7. 7. D · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
  8. 8. A · Kryptiniams acikliniams grafams

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