Užduočių lapas tema Duomenų struktūros su atsakymais

Nemokamas spausdinamas užduočių lapas tema Duomenų struktūros: 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

Kuri duomenų struktūra veikia principu „paskutinis įėjo – pirmas išėjo“ (LIFO)?

  1. AEilė
  2. BStekas
  3. CSusietasis sąrašas
  4. DMaišos lentelė
2.Lengvas

Kuri duomenų struktūra labiausiai tinka teksto redaktoriaus funkcijai „atšaukti“ (undo)?

  1. AGrafas
  2. BEilė
  3. CStekas
  4. DMaišos aibė
3.Lengvas

Kas saugoma kiekvienai viršūnei grafą vaizduojant gretimumo sąrašais?

  1. AV loginių reikšmių eilutė
  2. BJos kaimyninių viršūnių sąrašas
  3. CTrumpiausias kelias iki kiekvienos kitos viršūnės
  4. DBendras grafo briaunų skaičius
4.Vidutinis

Kur yra mazgo su indeksu i tėvas dvejetainėje krūvoje, saugomoje masyve nuo indekso 0?

  1. AIndeksu i − 1
  2. BIndeksu ⌊i / 2⌋ + 1
  3. CIndeksu ⌊(i − 1) / 2⌋
  4. DIndeksu 2i + 1
5.Vidutinis

7 dydžio maišos lentelė naudoja h(k) = k mod 7 ir tiesinį zondavimą. Kur saugomas 17, įterpus 10?

  1. AIndeksu 0
  2. BIndeksu 3
  3. CIndeksu 4
  4. DIndeksu 6
6.Vidutinis

Kodėl dvejetainę krūvą galima saugoti masyve be jokių rodyklių?

  1. ATai pilnas dvejetainis medis, todėl pozicijas nusako paprastos indeksų formulės
  2. BMasyvai automatiškai laiko raktus surikiuotus, todėl rodyklių nereikia
  3. CVisi krūvos raktai lygūs
  4. DKrūvose niekada nebūna daugiau kaip 100 elementų
7.Sunkus

Kuris teiginys apie rikiavimą krūva (heapsort) teisingas?

  1. AJis stabilus ir jam reikia O(n) papildomos atminties
  2. BJam reikia dvejetainio paieškos medžio kaip papildomos atminties, todėl jis naudoja O(n) papildomos atminties
  3. CSu bet kokia įvestimi jis veikia per O(n)
  4. DJis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus
8.Sunkus

Kokia blogiausio atvejo vienos find operacijos kaina union-find struktūroje su n elementų, nenaudojant jungimo pagal rangą ir kelio suspaudimo?

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

Atsakymai

  1. 1. B · Stekas
  2. 2. C · Stekas
  3. 3. B · Jos kaimyninių viršūnių sąrašas
  4. 4. C · Indeksu ⌊(i − 1) / 2⌋
  5. 5. C · Indeksu 4
  6. 6. A · Tai pilnas dvejetainis medis, todėl pozicijas nusako paprastos indeksų formulės
  7. 7. D · Jis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus
  8. 8. C · O(n)

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