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

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

Koks yra rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

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

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

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

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu 2 ilgio masyvu
  2. BSu atsitiktinės tvarkos masyvu
  3. CSu masyvu, kurio visi elementai skirtingi
  4. DSu jau surikiuotu masyvu
6.Vidutinis

Dinaminis programavimas naudingas, kai uždavinys turi:

  1. ATik atsitiktinius įvesties duomenis
  2. BVieną ciklą
  3. CPersidengiančius poproblemius ir optimalią postruktūrą
  4. DVisai jokių poproblemių, todėl jį galima išspręsti vienu žingsniu
7.Sunkus

Kuris algoritmas randa minimalų jungiamąjį medį, pakartotinai pridėdamas pigiausią briauną, kuri nesudaro ciklo?

  1. AKruskalo algoritmas
  2. BDijkstros algoritmas
  3. CFloido–Voršalo algoritmas
  4. DPrimo algoritmas, pradedant nuo vienos viršūnės
8.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. CIšsprendžiamas per polinominį laiką
  4. DNepriklauso NP, bet yra sunkesnis už visus NP uždavinius, pvz., sustojimo problema

Atsakymai

  1. 1. B · O(1)
  2. 2. B · O(n log n)
  3. 3. B · 6 sekundes
  4. 4. C · O(n)
  5. 5. D · Su jau surikiuotu masyvu
  6. 6. C · Persidengiančius poproblemius ir optimalią postruktūrą
  7. 7. A · Kruskalo algoritmas
  8. 8. B · Priklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką

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