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

Ką reiškia, jei operacija atliekama per O(1) laiką?

  1. AJos vykdymo laikas nedidėja didėjant įvesties dydžiui
  2. BJi visada trunka lygiai vieną sekundę
  3. CJą galima vykdyti tik vieną kartą
  4. DJi apdoroja lygiai vieną elementą per vykdymo sekundę
2.Lengvas

Ką reiškia f(n) = Θ(g(n))?

  1. Af auga griežtai lėčiau už g
  2. Bf auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  3. Cf visada mažesnė už g su kiekvienu n, todėl g riboja ją iš viršaus, bet niekada iš apačios
  4. Df auga griežtai greičiau už g
3.Lengvas

Kam lygus log₂ 1024?

  1. A32
  2. B10
  3. C12
  4. D512
4.Vidutinis

Vieną kartą surikiuojate n elementų masyvą, o tada dvejetaine paieška atsakote į k priklausomybės užklausų. Kokia bendra kaina?

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

Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?

  1. APirmiausia pasirinkti trumpiausią veiklą
  2. BPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  3. CPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
  4. DPasirinkti anksčiausiai prasidedančią veiklą
6.Vidutinis

Surikiuotame masyve ieškote dviejų elementų, kurių suma lygi tikslinei, judindami po vieną rodyklę nuo kiekvieno galo į vidų. Koks laiko sudėtingumas?

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

Ką nustatė Cooko–Levino teorema?

  1. ALoginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  2. BStabdymo problema yra neišsprendžiama
  3. CKiekvieną NP uždavinį galima išspręsti per eksponentinį laiką
  4. DP nelygu NP
8.Sunkus

Topologinis rikiavimas galimas tik:

  1. ANekryptiniams grafams
  2. BKryptiniams acikliniams grafams
  3. CPilniesiems grafams
  4. DGrafams su neigiamais svoriais

Atsakymai

  1. 1. A · Jos vykdymo laikas nedidėja didėjant įvesties dydžiui
  2. 2. B · f auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
  3. 3. B · 10
  4. 4. C · O(n log n + k log n)
  5. 5. B · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  6. 6. D · O(n)
  7. 7. A · Loginio įvykdomumo uždavinys (SAT) yra NP-pilnas
  8. 8. B · Kryptiniams acikliniams grafams

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