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

Ką apibūdina vykdymo laikas vidutiniu atveju?

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

Kuris žymėjimas nusako apatinį augimo rėžį?

  1. AO (didysis O)
  2. Bo (mažasis o)
  3. CΩ (didžioji Omega)
  4. DΘ (didžioji Teta)
3.Lengvas

Algoritmo vykdymo laikas yra O(n). Kaip vadinamas toks augimas?

  1. ATiesinis
  2. BPastovus
  3. CLogaritminis
  4. DKvadratinis
4.Vidutinis

Kuris rikiavimo algoritmas yra stabilus?

  1. AGreitasis rikiavimas (įprasta versija vietoje)
  2. BRikiavimas išrinkimu (įprasta versija)
  3. CRikiavimas suliejimu
  4. DRikiavimas krūva
5.Vidutinis

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

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

Kodėl didžiojo O žymėjime logaritmo pagrindas paprastai nenurodomas, kaip O(log n)?

  1. ASkirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  2. BPagrindas svarbus tik mažiems n
  3. CLogaritmai visada apvalinami iki sveikųjų skaičių
  4. DVisų logaritmų informatikoje pagrindas yra 10, todėl jis numanomas
7.Sunkus

Kodėl Dijkstros algoritmas gali duoti neteisingus rezultatus, kai kai kurie briaunų svoriai neigiami?

  1. AViršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią
  2. BTies kiekviena neigiama briauna jis patenka į begalinį ciklą
  3. CNeigiamų skaičių negalima saugoti prioritetinėje eilėje
  4. DJis veikia tik su nekryptiniais grafais
8.Sunkus

Koks yra Dijkstros algoritmo su dvejetaine krūva vykdymo laikas grafui su V viršūnių ir E briaunų?

  1. AO(V × E)
  2. BO(V³)
  3. CO((V + E) log V)
  4. DO(V + E)

Atsakymai

  1. 1. A · Tikėtiną laiką esant tam tikram n dydžio įvesčių skirstiniui
  2. 2. C · Ω (didžioji Omega)
  3. 3. A · Tiesinis
  4. 4. C · Rikiavimas suliejimu
  5. 5. A · Optimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
  6. 6. A · Skirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  7. 7. A · Viršūnė galutinai nustatoma ją išėmus, bet vėlesnė neigiama briauna dar galėtų duoti jai trumpesnį kelią
  8. 8. C · O((V + E) log V)

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