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 medžio šaknis?

  1. AMazgas be vaikų
  2. BBet kuris mazgas viduryje
  3. CViršutinis mazgas, neturintis tėvo
  4. DMazgas su didžiausia reikšme
2.Lengvas

Dvejetainiame paieškos medyje mazgo kairiojo pomedžio reikšmės yra:

  1. ALygios mazgo reikšmei
  2. BAtsitiktine tvarka
  3. CDidesnės už mazgo reikšmę
  4. DMažesnės už mazgo reikšmę
3.Lengvas

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

  1. ATrumpiausias kelias iki kiekvienos kitos viršūnės
  2. BBendras grafo briaunų skaičius
  3. CJos kaimyninių viršūnių sąrašas
  4. DV loginių reikšmių eilutė
4.Vidutinis

Kiek atminties naudoja grafo su V viršūnių gretimumo matrica?

  1. AO(V²)
  2. BO(V + E)
  3. CO(E)
  4. DO(log V)
5.Vidutinis

Kaip naujas elementas įterpiamas į dvejetainę krūvą?

  1. AĮterpiamas į surikiuotą poziciją, pastumiant visus didesnius elementus viena vieta į dešinę
  2. BPadedamas šaknyje ir leidžiamas žemyn
  3. CPadedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę
  4. DVisa krūva perstatoma iš naujo
6.Vidutinis

Dvejetainio medžio šaknis yra 1, jos kairysis vaikas 2, dešinysis 3; mazgas 2 turi vaikus 4 (kairįjį) ir 5 (dešinįjį). Koks postorder apėjimas?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C5 4 3 2 1
  4. D1 2 4 5 3
7.Sunkus

Ką skleidžiamasis medis (splay tree) atlieka po kiekvienos prieigos?

  1. APerstato visą medį į subalansuotą formą
  2. BPerspalvina paieškos kelio mazgus
  3. CPerkelia pasiektą mazgą į lapą
  4. DPosūkiais iškelia pasiektą mazgą į šaknį
8.Sunkus

Struktūros union-find (nesikertančios aibės) su jungimu pagal rangą ir kelio suspaudimu amortizuota vienos operacijos kaina yra:

  1. AO(n²)
  2. BO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
  3. CO(n)
  4. DTiksliai O(log n)

Atsakymai

  1. 1. C · Viršutinis mazgas, neturintis tėvo
  2. 2. D · Mažesnės už mazgo reikšmę
  3. 3. C · Jos kaimyninių viršūnių sąrašas
  4. 4. A · O(V²)
  5. 5. C · Padedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę
  6. 6. A · 4 5 2 3 1
  7. 7. D · Posūkiais iškelia pasiektą mazgą į šaknį
  8. 8. B · O(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi

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