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ą reiškia f(n) = Θ(g(n))?

  1. Af auga griežtai greičiau už g
  2. Bf auga griežtai lėčiau už g
  3. Cf visada mažesnė už g su kiekvienu n, todėl g riboja ją iš viršaus, bet niekada iš apačios
  4. Df auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
2.Lengvas

O(n) algoritmas, kai n = 1 milijonas, trunka 3 sekundes. Maždaug kiek jis truks, kai n = 2 milijonai?

  1. A12 sekundžių
  2. B9 sekundes
  3. C3 sekundes
  4. D6 sekundes
3.Lengvas

Kas yra perrinkimo (brute force) algoritmas?

  1. AAlgoritmas, atsitiktinai spėjantis atsakymą
  2. BAlgoritmas, kuris visada naudoja rekursiją
  3. CAlgoritmas, veikiantis daugelyje procesorių
  4. DAlgoritmas, išbandantis visus galimus kandidatinius sprendinius
4.Vidutinis

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

  1. AApie log₂ n
  2. BApie n / 2
  3. CApie √n
  4. DApie n
6.Vidutinis

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

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

Kuris NP klasės apibrėžimas teisingas?

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

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

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

Atsakymai

  1. 1. D · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  2. 2. D · 6 sekundes
  3. 3. D · Algoritmas, išbandantis visus galimus kandidatinius sprendinius
  4. 4. B · O(n log n)
  5. 5. A · Apie log₂ n
  6. 6. D · O(n)
  7. 7. A · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
  8. 8. A · 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.