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

Kas yra perrinkimo (brute force) algoritmas?

  1. AAlgoritmas, veikiantis daugelyje procesorių
  2. BAlgoritmas, išbandantis visus galimus kandidatinius sprendinius
  3. CAlgoritmas, atsitiktinai spėjantis atsakymą
  4. DAlgoritmas, kuris visada naudoja rekursiją
2.Lengvas

Ką apibūdina algoritmo vykdymo laikas blogiausiu atveju?

  1. ADidžiausią laiką tarp visų n dydžio įvesčių
  2. BLaiką lėtame kompiuteryje
  3. CTikėtiną laiką su atsitiktine n dydžio įvestimi
  4. DLaiką su mažiausia įvestimi
3.Lengvas

Kuris žymėjimas nusako apatinį augimo rėžį?

  1. Ao (mažasis o)
  2. BO (didysis O)
  3. CΩ (didžioji Omega)
  4. DΘ (didžioji Teta)
4.Vidutinis

Kuris algoritmas randa trumpiausius kelius iš vienos pradinės viršūnės grafe, kurio briaunų svoriai neneigiami?

  1. AVisais atvejais būtinas Belmano–Fordo algoritmas
  2. BKruskalo algoritmas
  3. CDijkstros algoritmas
  4. DPaieška gilyn (DFS)
5.Vidutinis

Koks yra amortizuotas laiko sudėtingumas pridedant elementą į dinaminio masyvo, kuris prisipildęs padvigubina savo talpą, galą?

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

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

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

Kuris teiginys apie P ir NP yra teisingas?

  1. AĮrodyta, kad P ≠ NP
  2. BNP reiškia „nepolinominis“ (not polynomial)
  3. CNP uždavinių sprendinių negalima greitai patikrinti
  4. DKiekvienas P klasės uždavinys taip pat priklauso NP
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 · Algoritmas, išbandantis visus galimus kandidatinius sprendinius
  2. 2. A · Didžiausią laiką tarp visų n dydžio įvesčių
  3. 3. C · Ω (didžioji Omega)
  4. 4. C · Dijkstros algoritmas
  5. 5. B · O(1)
  6. 6. B · O(n)
  7. 7. D · Kiekvienas P klasės uždavinys taip pat priklauso NP
  8. 8. A · Θ(n log² n)

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