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 algoritmo vykdymo laikas blogiausiu atveju?

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

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

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

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

  1. ADidžioji Teta
  2. BDidžioji Omega
  3. CMažoji omega
  4. DDidysis O
4.Vidutinis

Ką apskaičiuoja Floydo–Warshallo algoritmas ir kaip greitai?

  1. ATrumpiausius kelius tarp visų viršūnių porų per O(V³)
  2. BTopologinę tvarką per O(V²)
  3. CTrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)
  4. DMinimalų jungiamąjį medį per O(E log V)
5.Vidutinis

Kiek steko vietos naudoja paprasta rekursinė faktorialo funkcija fact(n) = n × fact(n − 1)?

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

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for (j = i; j ≤ n; j = j + i) atlikti O(1) darbą?

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

Kuris NP klasės apibrėžimas teisingas?

  1. AUždaviniai, kurių negalima išspręsti per polinominį laiką
  2. BUždaviniai, kurių neišsprendžia joks algoritmas
  3. CSprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
  4. DUždaviniai, kurie nėra polinominiai

Atsakymai

  1. 1. D · Didžiausią laiką tarp visų n dydžio įvesčių
  2. 2. A · O(log n)
  3. 3. D · Didysis O
  4. 4. A · Trumpiausius kelius tarp visų viršūnių porų per O(V³)
  5. 5. A · O(n)
  6. 6. C · O(n)
  7. 7. C · O(n log n)
  8. 8. C · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką

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