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 rekursija?

  1. ARikiavimo metodas
  2. BCiklas, kuris niekada nesibaigia
  3. CFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  4. DDuomenų struktūros tipas
2.Lengvas

Uždavinys paprastai vadinamas praktiškai išsprendžiamu (tractable), jei:

  1. AJį galima išspręsti per pastovų laiką
  2. BJį galima išspręsti per polinominį laiką
  3. CJis neturi sprendinio
  4. DJį galima išspręsti tik išbandant visas galimybes
3.Lengvas

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

Koks yra LSD pozicinio rikiavimo (radix sort) vykdymo laikas n sveikųjų skaičių, turinčių d skaitmenų k pagrindo sistemoje?

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

Maždaug kiek palyginimų blogiausiu atveju reikia dvejetainei paieškai surikiuotame 1,000,000 elementų masyve?

  1. AApie 20
  2. BApie 1,000
  3. CApie 500,000
  4. DApie 100
6.Vidutinis

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

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

Sustojimo problema parodo, kad:

  1. AKai kurios programos greitesniuose kompiuteriuose veikia greičiau, todėl sustojimas priklauso nuo aparatinės įrangos
  2. BJoks algoritmas negali kiekvienai programai ir įvesčiai nuspręsti, ar ji sustos
  3. CKiekviena programa anksčiau ar vėliau sustoja
  4. DCiklų reikėtų vengti
8.Sunkus

Ką reikia padaryti, norint parodyti, kad naujas uždavinys X yra NP-sunkus?

  1. AParodyti, kad X galima patikrinti per polinominį laiką
  2. BParodyti, kad X neturi polinominio algoritmo mažoms įvestims
  3. CPer polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X
  4. DPer polinominį laiką redukuoti X į žinomą NP-sunkų uždavinį

Atsakymai

  1. 1. C · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  2. 2. B · Jį galima išspręsti per polinominį laiką
  3. 3. C · O(1)
  4. 4. C · O(d(n + k))
  5. 5. A · Apie 20
  6. 6. C · Su jau surikiuotu masyvu
  7. 7. B · Joks algoritmas negali kiekvienai programai ir įvesčiai nuspręsti, ar ji sustos
  8. 8. C · Per polinominį laiką redukuoti žinomą NP-sunkų uždavinį į X

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