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

Kas yra maišos lentelės užpildymo koeficientas (load factor)?

  1. AIki šiol įvykusių kolizijų skaičius
  2. BKibirų skaičius, padalytas iš vidutinio saugomų raktų ilgio
  3. CLaikas, reikalingas lentelei įkelti iš disko
  4. DSaugomų elementų skaičius, padalytas iš kibirų skaičiaus
2.Lengvas

Kuri duomenų struktūra naudojama medžio apėjimui lygmenimis (level-order)?

  1. APrioritetinė eilė
  2. BEilė
  3. CStekas
  4. DMaišos lentelė
3.Lengvas

Vienkrypčiame susietajame sąraše kiekvienas mazgas turi:

  1. ATik duomenis
  2. BDuomenis ir nuorodą į kitą mazgą
  3. CDuomenis ir nuorodas į visus kitus mazgus
  4. DDuomenis ir indeksą
4.Vidutinis

Raktai 50, 30, 70, 20, 40 šia tvarka įterpiami į tuščią dvejetainį paieškos medį. Koks yra 30 kairysis vaikas?

  1. A40
  2. B70
  3. C20
  4. D50
5.Vidutinis

Kodėl masyvo apėjimas praktikoje dažnai daug greitesnis nei tokio pat ilgio susietojo sąrašo apėjimas?

  1. AMasyvai reikšmėms palyginti naudoja mažiau instrukcijų
  2. BSusietieji sąrašai visada saugo elementus diske
  3. CMasyvo apėjimas iš viso yra O(1), o susietojo sąrašo – O(n)
  4. DMasyvo elementai išdėstyti vientisai, todėl gerai išnaudoja procesoriaus podėlį (cache)
6.Vidutinis

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

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

Kuri duomenų struktūra leidžia LRU (least recently used) podėlį su O(1) get ir put operacijomis?

  1. AVienas surikiuotas masyvas
  2. BTik dvejetainis paieškos medis
  3. CMaišos žemėlapis kartu su dvikrypčiu susietuoju sąrašu
  4. DTik stekas
8.Sunkus

Kahno topologinio rikiavimo algoritmas pakartotinai šalina viršūnes, kurių įeinantis laipsnis lygus 0. Kuri struktūra laiko šias viršūnes?

  1. AGretimumo matrica, žyminti, kurios viršūnės jau pašalintos
  2. BVisų aplankytų briaunų stekas
  3. CPagal išeinantį laipsnį sutvarkyta max krūva
  4. DViršūnių, kurių įeinantis laipsnis 0, eilė (ar bet kuri kolekcija)

Atsakymai

  1. 1. D · Saugomų elementų skaičius, padalytas iš kibirų skaičiaus
  2. 2. B · Eilė
  3. 3. B · Duomenis ir nuorodą į kitą mazgą
  4. 4. C · 20
  5. 5. D · Masyvo elementai išdėstyti vientisai, todėl gerai išnaudoja procesoriaus podėlį (cache)
  6. 6. C · Tai pilnas dvejetainis medis, todėl pozicijas nusako paprastos indeksų formulės
  7. 7. C · Maišos žemėlapis kartu su dvikrypčiu susietuoju sąrašu
  8. 8. D · Viršūnių, kurių įeinantis laipsnis 0, eilė (ar bet kuri kolekcija)

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