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 skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

Koks yra rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(n log n)
3.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)
4.Vidutinis

Dinaminis programavimas naudingas, kai uždavinys turi:

  1. AVisai jokių poproblemių, todėl jį galima išspręsti vienu žingsniu
  2. BPersidengiančius poproblemius ir optimalią postruktūrą
  3. CVieną ciklą
  4. DTik atsitiktinius įvesties duomenis
5.Vidutinis

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

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

Kam lygus rekurentinės lygties T(n) = 2T(n − 1) + O(1) sprendinys?

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

Trumpiausius paprastuosius kelius galima rasti per polinominį laiką. Kas žinoma apie ilgiausio paprastojo kelio tarp dviejų viršūnių paiešką bendrajame grafe?

  1. AJį galima išspręsti Dijkstros algoritmu su priešingo ženklo svoriais
  2. BJis visada išsprendžiamas per O(V + E)
  3. CTai NP-sunkus uždavinys
  4. DJis neišsprendžiamas
8.Sunkus

Topologinis rikiavimas galimas tik:

  1. APilniesiems grafams
  2. BNekryptiniams grafams
  3. CKryptiniams acikliniams grafams
  4. DGrafams su neigiamais svoriais

Atsakymai

  1. 1. A · O(n + k)
  2. 2. D · O(n log n)
  3. 3. A · O(log n)
  4. 4. B · Persidengiančius poproblemius ir optimalią postruktūrą
  5. 5. D · Skirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  6. 6. D · O(2ⁿ)
  7. 7. C · Tai NP-sunkus uždavinys
  8. 8. C · Kryptiniams acikliniams grafams

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