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 iš šių vykdymo laikų yra polinominis?

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

Koks yra 3n² + 5n + 2 didysis O?

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

Kas yra rekursija?

  1. ADuomenų struktūros tipas
  2. BCiklas, kuris niekada nesibaigia
  3. CFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. DRikiavimo metodas
4.Vidutinis

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

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

Vieną kartą surikiuojate n elementų masyvą, o tada dvejetaine paieška atsakote į k priklausomybės užklausų. Kokia bendra kaina?

  1. AO(n log n + k log n)
  2. BO(nk)
  3. CO(k n log n)
  4. DO(n + k)
6.Vidutinis

Kiek lygmenų turi rikiavimo suliejimu rekursija n elementų masyvui?

  1. AApie log₂ n
  2. BApie n / 2
  3. CApie √n
  4. DApie n
7.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. BRekursijos taikymas tik kairiajai pusei
  3. CAtraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį
  4. DVisada pirmojo elemento parinkimas
8.Sunkus

Kuris algoritmas randa minimalų jungiamąjį medį, pakartotinai pridėdamas pigiausią briauną, kuri nesudaro ciklo?

  1. AFloido–Voršalo algoritmas
  2. BDijkstros algoritmas
  3. CKruskalo algoritmas
  4. DPrimo algoritmas, pradedant nuo vienos viršūnės

Atsakymai

  1. 1. D · O(n³)
  2. 2. C · O(n²)
  3. 3. C · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. 4. B · O(n)
  5. 5. A · O(n log n + k log n)
  6. 6. A · Apie log₂ n
  7. 7. C · Atraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį
  8. 8. C · Kruskalo algoritmas

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