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

Erdvės (atminties) sudėtingumas matuoja:

  1. AFizinį kompiuterio dydį
  2. BProgramos failo užimamą vietą diske jį sukompiliavus
  3. CKiek atminties algoritmui reikia didėjant įvesties duomenims
  4. DKodo eilučių skaičių
2.Lengvas

Koks yra rikiavimo įterpimu laiko sudėtingumas blogiausiu atveju?

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

Koks yra paieškos gilyn laiko sudėtingumas grafui, saugomam gretimumo sąrašais?

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

Koks yra dviejų n × n matricų daugybos standartiniu trigubu ciklu laiko sudėtingumas?

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

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

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

Kodėl didžiojo O žymėjime logaritmo pagrindas paprastai nenurodomas, kaip O(log n)?

  1. ALogaritmai visada apvalinami iki sveikųjų skaičių
  2. BVisų logaritmų informatikoje pagrindas yra 10, todėl jis numanomas
  3. CPagrindas svarbus tik mažiems n
  4. DSkirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
7.Sunkus

Uždavinys yra NP-pilnas, jei jis:

  1. ANeišsprendžiamas
  2. BPriklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką
  3. CNepriklauso NP, bet yra sunkesnis už visus NP uždavinius, pvz., sustojimo problema
  4. DIšsprendžiamas per polinominį laiką
8.Sunkus

Ką nustatė Cooko–Levino teorema?

  1. AStabdymo problema yra neišsprendžiama
  2. BP nelygu NP
  3. CLoginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  4. DKiekvieną NP uždavinį galima išspręsti per eksponentinį laiką

Atsakymai

  1. 1. C · Kiek atminties algoritmui reikia didėjant įvesties duomenims
  2. 2. A · O(n²)
  3. 3. B · O(V + E)
  4. 4. A · O(n³)
  5. 5. D · Ω(n log n)
  6. 6. D · Skirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  7. 7. B · Priklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką
  8. 8. C · Loginio įvykdomumo uždavinys (SAT) yra NP-pilnas

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