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

Koks yra rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

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

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

Koks yra dvejetainės paieškos surikiuotame masyve laiko sudėtingumas?

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

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

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

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

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

Rekurentinės lygties T(n) = 2T(n/2) + O(n) sprendinys yra:

  1. AO(log n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
7.Sunkus

Topologinis rikiavimas galimas tik:

  1. ANekryptiniams grafams
  2. BGrafams su neigiamais svoriais
  3. CPilniesiems grafams
  4. DKryptiniams acikliniams grafams
8.Sunkus

Kodėl dvejetainė paieška vienkrypčiame susietajame sąraše neužtikrina O(log n) laiko?

  1. ADvejetainei paieškai reikia bent dvigubai daugiau atminties
  2. BIki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  3. CSusietųjų sąrašų negalima surikiuoti
  4. DSusietojo sąrašo mazgų palyginimai lėtesni

Atsakymai

  1. 1. B · O(n)
  2. 2. C · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  3. 3. D · O(log n)
  4. 4. B · O(log n)
  5. 5. B · O(n)
  6. 6. B · O(n log n)
  7. 7. D · Kryptiniams acikliniams grafams
  8. 8. B · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą

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