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

Ką atlieka steko operacija peek (arba top)?

  1. APašalina visus steko elementus
  2. BGrąžina viršutinį elementą jo nepašalindama
  3. CGrąžina apatinį steko elementą
  4. DPašalina viršutinį elementą ir jį grąžina
2.Lengvas

Kiek briaunų turi medis su n mazgų?

  1. A2n
  2. Bn + 1
  3. Cn − 1
  4. Dn
3.Lengvas

Ką saugo atvaizdis (žodynas, map)?

  1. ARaktų ir reikšmių poras su unikaliais raktais
  2. BTik reikšmes įterpimo tvarka
  3. CPagal dydį surikiuotas reikšmes
  4. DVienodų raktų poras
4.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. BStekas
  3. CNesurikiuotas susietasis sąrašas
  4. DSubalansuotas dvejetainis paieškos medis
5.Vidutinis

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

  1. APaskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  2. BPašalinamas paskutinis masyvo elementas
  3. CNaujo minimumo ieškoma visuose lapuose
  4. DPašalinama šaknis, o visi elementai pastumiami viena vieta į kairę
6.Vidutinis

Turite nuorodą į mazgą sąrašo viduryje. Kuriame sąraše jį galite pašalinti per O(1)?

  1. ASurikiuotame masyve
  2. BDinaminiame masyve
  3. CDvikrypčiame susietajame sąraše
  4. DVienkrypčiame susietajame sąraše
7.Sunkus

Koks pagrindinis šuolių sąrašo (skip list) pranašumas prieš surikiuotą susietąjį sąrašą?

  1. ATikėtina O(log n) paieška naudojant kelis į priekį rodančių rodyklių lygmenis
  2. BJis saugo raktus be tvarkos
  3. CGarantuota O(1) paieška, nes kiekvienas mazgas saugo rodyklę į kiekvieną kitą mazgą
  4. DJis nenaudoja papildomos atminties
8.Sunkus

Kiek laiko užtrunka bet kurio rakto paieška n elementų dvejetainėje min krūvoje?

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

Atsakymai

  1. 1. B · Grąžina viršutinį elementą jo nepašalindama
  2. 2. C · n − 1
  3. 3. A · Raktų ir reikšmių poras su unikaliais raktais
  4. 4. D · Subalansuotas dvejetainis paieškos medis
  5. 5. A · Paskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  6. 6. C · Dvikrypčiame susietajame sąraše
  7. 7. A · Tikėtina O(log n) paieška naudojant kelis į priekį rodančių rodyklių lygmenis
  8. 8. A · O(n)

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