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. ADuomenų struktūros tipas
  2. BFunkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  3. CCiklas, kuris niekada nesibaigia
  4. DRikiavimo metodas
2.Lengvas

Koks yra rikiavimo skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

Kas yra algoritmas?

  1. ADuomenų struktūra, sauganti skaičius
  2. BProgramavimo kalba, sukurta matematinėms formulėms rašyti
  3. CBet kokia kompiuterio programa su grafine sąsaja
  4. DBaigtinė tiksliai apibrėžtų žingsnių seka, sprendžianti uždavinį
4.Vidutinis

Kuris teiginys apie rekursinę funkciją be pasiekiamo bazinio atvejo teisingas?

  1. AJi vis kviečia save, kol perpildomas kvietimų stekas
  2. BKompiliatorius visada ją paverčia ciklu, kuris saugiai pasibaigia
  3. CJi veikia per O(1) laiką
  4. DJi automatiškai grąžina 0
5.Vidutinis

Koks yra n-tojo Fibonačio skaičiaus skaičiavimo laiko sudėtingumas, naudojant lentelę „iš apačios į viršų“?

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

Kuris teiginys apie P ir NP yra teisingas?

  1. AĮrodyta, kad P ≠ NP
  2. BNP uždavinių sprendinių negalima greitai patikrinti
  3. CNP reiškia „nepolinominis“ (not polynomial)
  4. DKiekvienas P klasės uždavinys taip pat priklauso NP
8.Sunkus

Kodėl dvejetainė paieška vienkrypčiame susietajame sąraše neužtikrina O(log n) laiko?

  1. ASusietųjų sąrašų negalima surikiuoti
  2. BDvejetainei paieškai reikia bent dvigubai daugiau atminties
  3. CIki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  4. DSusietojo sąrašo mazgų palyginimai lėtesni

Atsakymai

  1. 1. B · Funkcija, kuri iškviečia pati save su mažesniais įvesties duomenimis
  2. 2. B · O(n + k)
  3. 3. D · Baigtinė tiksliai apibrėžtų žingsnių seka, sprendžianti uždavinį
  4. 4. A · Ji vis kviečia save, kol perpildomas kvietimų stekas
  5. 5. A · O(n)
  6. 6. B · O(n)
  7. 7. D · Kiekvienas P klasės uždavinys taip pat priklauso NP
  8. 8. C · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą

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