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

Maišos lentelė (hash table) saugo duomenis kaip:

  1. ARakto ir reikšmės poras, randamas maišos funkcija
  2. BTik surikiuotą sąrašą
  3. CFiksuoto ilgio eilutę
  4. DMedį su sutvarkytais raktais
2.Lengvas

Kas grafe yra ciklas?

  1. ABriauna, kurios svoris lygus nuliui
  2. BKelias, prasidedantis ir pasibaigiantis toje pačioje viršūnėje
  3. CViršūnė be briaunų
  4. DKelias, aplankantis kiekvieną viršūnę
3.Lengvas

Kas nekryptiniame grafe yra viršūnės laipsnis?

  1. AGrafo viršūnių skaičius
  2. BJos pozicija gretimumo sąraše
  3. CIlgiausio iš jos einančio kelio ilgis
  4. DSu ja sujungtų briaunų skaičius
4.Vidutinis

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

  1. A50
  2. B40
  3. C70
  4. D20
5.Vidutinis

Programai reikia greitos paieškos, taip pat reikia išvardyti raktus surikiuota tvarka ir atsakyti į intervalų užklausas. Kuri struktūra tinka geriausiai?

  1. AMaišos lentelė
  2. BNesurikiuotas susietasis sąrašas
  3. CSubalansuotas dvejetainis paieškos medis
  4. DStekas
6.Vidutinis

Kaip dvejetainėje min krūvoje veikia extract-min?

  1. APašalinamas paskutinis masyvo elementas
  2. BPaskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  3. CPašalinama šaknis, o visi elementai pastumiami viena vieta į kairę
  4. DNaujo minimumo ieškoma visuose lapuose
7.Sunkus

Įterpus raktą į AVL medį, mazgo kairysis pomedis tampa per aukštas, o naujas raktas pateko į jo kairiojo vaiko kairįjį pomedį (kairė–kairė atvejis). Koks taisymas taikomas?

  1. AVienas dešinysis posūkis nesubalansuotame mazge
  2. BMazgo ir jo vaiko perspalvinimas
  3. CVienas kairysis posūkis nesubalansuotame mazge
  4. DKairysis posūkis vaike, tada dešinysis posūkis mazge
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(α(n))
  3. CO(1)
  4. DO(n)

Atsakymai

  1. 1. A · Rakto ir reikšmės poras, randamas maišos funkcija
  2. 2. B · Kelias, prasidedantis ir pasibaigiantis toje pačioje viršūnėje
  3. 3. D · Su ja sujungtų briaunų skaičius
  4. 4. D · 20
  5. 5. C · Subalansuotas dvejetainis paieškos medis
  6. 6. B · Paskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  7. 7. A · Vienas dešinysis posūkis nesubalansuotame mazge
  8. 8. D · O(n)

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