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 suliejimu laiko sudėtingumas blogiausiu atveju?

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

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

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

Erdvės (atminties) sudėtingumas matuoja:

  1. AProgramos failo užimamą vietą diske jį sukompiliavus
  2. BFizinį kompiuterio dydį
  3. CKodo eilučių skaičių
  4. DKiek atminties algoritmui reikia didėjant įvesties duomenims
4.Vidutinis

Koks yra LSD pozicinio rikiavimo (radix sort) vykdymo laikas n sveikųjų skaičių, turinčių d skaitmenų k pagrindo sistemoje?

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

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

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

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

  1. AΩ(n²)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n log n)
7.Sunkus

Koks yra Dijkstros algoritmo su dvejetaine krūva vykdymo laikas grafui su V viršūnių ir E briaunų?

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

Kuris teiginys apie P ir NP yra teisingas?

  1. AĮrodyta, kad P ≠ NP
  2. BKiekvienas P klasės uždavinys taip pat priklauso NP
  3. CNP reiškia „nepolinominis“ (not polynomial)
  4. DNP uždavinių sprendinių negalima greitai patikrinti

Atsakymai

  1. 1. D · O(n log n)
  2. 2. B · O(n)
  3. 3. D · Kiek atminties algoritmui reikia didėjant įvesties duomenims
  4. 4. D · O(d(n + k))
  5. 5. C · Apie log₂ n
  6. 6. D · Ω(n log n)
  7. 7. A · O((V + E) log V)
  8. 8. B · Kiekvienas P klasės uždavinys taip pat priklauso NP

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