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

Kuris rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

  1. AGreitasis rikiavimas (quicksort)
  2. BBurbuliuko rikiavimas
  3. CRikiavimas įterpimu
  4. DRikiavimas suliejimu
2.Lengvas

Kokie yra trys „skaldyk ir valdyk“ algoritmo žingsniai?

  1. ASpėk, tikrink, kartok
  2. BSkaityk, skaičiuok, rašyk
  3. CSurikiuok, ieškok, grąžink
  4. DPadalyk, išspręsk, sujunk
3.Lengvas

Koks yra rikiavimo įterpimu laiko sudėtingumas blogiausiu atveju?

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

Ar teisinga sakyti, kad O(n²) algoritmas yra ir O(n³)?

  1. ATaip, bet tik jei n mažesnis už 100
  2. BTaip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  3. CNe, nes dideliems n n³ mažesnis už n²
  4. DNe, nes didysis O visada turi nurodyti tikslų funkcijos augimo greitį
5.Vidutinis

Koks yra dviejų n × n matricų daugybos standartiniu trigubu ciklu laiko sudėtingumas?

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

Kodėl didžiojo O žymėjime logaritmo pagrindas paprastai nenurodomas, kaip O(log n)?

  1. APagrindas svarbus tik mažiems n
  2. BLogaritmai visada apvalinami iki sveikųjų skaičių
  3. CVisų logaritmų informatikoje pagrindas yra 10, todėl jis numanomas
  4. DSkirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
7.Sunkus

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for (j = i; j ≤ n; j = j + i) atlikti O(1) darbą?

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

Kuris teiginys apie P ir NP yra teisingas?

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

Atsakymai

  1. 1. A · Greitasis rikiavimas (quicksort)
  2. 2. D · Padalyk, išspręsk, sujunk
  3. 3. B · O(n²)
  4. 4. B · Taip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
  5. 5. D · O(n³)
  6. 6. D · Skirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
  7. 7. A · O(n log n)
  8. 8. A · Kiekvienas P klasės uždavinys taip pat priklauso NP

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