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 rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

  1. ARikiavimas įterpimu
  2. BGreitasis rikiavimas (quicksort)
  3. CRikiavimas suliejimu
  4. DBurbuliuko rikiavimas
2.Lengvas

Kiek papildomos atminties naudoja standartinis masyvu grįstas rikiavimas suliejimu?

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

Koks yra rikiavimo skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

Palyginimais pagrįsto rikiavimo apatinis rėžis blogiausiu atveju yra:

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n²)
  4. DΩ(n)
5.Vidutinis

Koks yra Bellmano–Fordo algoritmo laiko sudėtingumas grafui su V viršūnių ir E briaunų?

  1. AO(E log V)
  2. BO(V + E)
  3. CO(V³ × E)
  4. DO(V × E)
6.Vidutinis

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

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

Kokia amortizuotoji dvejetainio skaitiklio padidinimo kaina, žinant, kad vienas padidinimas gali pakeisti daug bitų?

  1. AO(1) vienam padidinimui
  2. BO(n log n) vienam padidinimui
  3. CO(n) vienam padidinimui
  4. DO(log n) vienam padidinimui
8.Sunkus

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

  1. AΘ(n log² n)
  2. BΘ(n)
  3. CΘ(n²)
  4. DΘ(n log n)

Atsakymai

  1. 1. B · Greitasis rikiavimas (quicksort)
  2. 2. A · O(n)
  3. 3. B · O(n + k)
  4. 4. A · Ω(n log n)
  5. 5. D · O(V × E)
  6. 6. C · O(n)
  7. 7. A · O(1) vienam padidinimui
  8. 8. A · Θ(n log² n)

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