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

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

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

Ką apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ALaiką lėtame kompiuteryje
  2. BLaiką su mažiausia įvestimi
  3. CTikėtiną laiką su atsitiktine n dydžio įvestimi
  4. DDidžiausią laiką tarp visų n dydžio įvesčių
3.Lengvas

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

  1. A2 sekundes
  2. B1 sekundę
  3. C8 sekundes
  4. D4 sekundes
4.Vidutinis

Maždaug kiek palyginimų blogiausiu atveju reikia dvejetainei paieškai surikiuotame 1,000,000 elementų masyve?

  1. AApie 20
  2. BApie 500,000
  3. CApie 1,000
  4. DApie 100
5.Vidutinis

Koks yra amortizuotas laiko sudėtingumas pridedant elementą į dinaminio masyvo, kuris prisipildęs padvigubina savo talpą, galą?

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

Kuris teiginys apie rekursinę funkciją be pasiekiamo bazinio atvejo teisingas?

  1. AJi veikia per O(1) laiką
  2. BJi automatiškai grąžina 0
  3. CJi vis kviečia save, kol perpildomas kvietimų stekas
  4. DKompiliatorius visada ją paverčia ciklu, kuris saugiai pasibaigia
7.Sunkus

Topologinis rikiavimas galimas tik:

  1. AGrafams su neigiamais svoriais
  2. BKryptiniams acikliniams grafams
  3. CNekryptiniams grafams
  4. DPilniesiems grafams
8.Sunkus

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

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

Atsakymai

  1. 1. D · O(2ⁿ)
  2. 2. D · Didžiausią laiką tarp visų n dydžio įvesčių
  3. 3. D · 4 sekundes
  4. 4. A · Apie 20
  5. 5. A · O(1)
  6. 6. C · Ji vis kviečia save, kol perpildomas kvietimų stekas
  7. 7. B · Kryptiniams acikliniams grafams
  8. 8. A · Po V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti

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