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

Kokia tvarka dvejetainio medžio apėjimas preorder aplanko mazgus?

  1. AMazgas, tada kairysis pomedis, tada dešinysis pomedis
  2. BKairysis pomedis, tada mazgas, tada dešinysis pomedis
  3. CLygmuo po lygmens nuo viršaus
  4. DKairysis pomedis, tada dešinysis pomedis, tada mazgas
2.Lengvas

Koks yra aibės, kaip abstrakčiojo duomenų tipo, apibrėžiantis bruožas?

  1. AJi leidžia prieigą tik viename gale
  2. BJi saugo elementus be pasikartojimų
  3. CJi saugo elementus surikiuota tvarka
  4. DJi saugo raktų ir reikšmių poras
3.Lengvas

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

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

Kurį abstraktųjį duomenų tipą Dijkstros algoritmas naudoja kitai apdorojamai viršūnei parinkti?

  1. AFIFO eilę
  2. BSteką
  3. CNesutvarkytą aibę
  4. DMin prioritetinę eilę
5.Vidutinis

Kokia rakto paieškos subalansuotame dvejetainiame paieškos medyje laiko sudėtingumas?

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

Dvejetainėje min krūvoje, saugomoje masyve (indeksai nuo 0), mazgo su indeksu i vaikai yra pozicijose:

  1. Ai/2 ir i/2 + 1
  2. B2i + 1 ir 2i + 2
  3. C2i ir 2i + 1
  4. Di + 1 ir i + 2
7.Sunkus

Kurią tiesinio zondavimo problemą dvigubas maišymas (double hashing) daugiausia sumažina?

  1. APoreikį saugoti raktus lentelėje
  2. BPirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
  3. CMaišos funkcijos poreikį
  4. DRakto reikšmės skaitymo O(n) kainą
8.Sunkus

Kodėl maišos lentelėje su atviruoju adresavimu šalinimas dažnai atliekamas naudojant „antkapio“ (tombstone) žymę?

  1. ADėl to lentelė tampa surikiuota
  2. BAntkapiai pagreitina maišymą
  3. CIštuštinus vietą, galėtų nutrūkti kitų raktų zondavimo seka
  4. DPašalinti raktai saugumo sumetimais turi būti laikomi amžinai, todėl vietų niekada negalima naudoti pakartotinai

Atsakymai

  1. 1. A · Mazgas, tada kairysis pomedis, tada dešinysis pomedis
  2. 2. B · Ji saugo elementus be pasikartojimų
  3. 3. D · Jos kaimyninių viršūnių sąrašas
  4. 4. D · Min prioritetinę eilę
  5. 5. D · O(log n)
  6. 6. B · 2i + 1 ir 2i + 2
  7. 7. B · Pirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
  8. 8. C · Ištuštinus vietą, galėtų nutrūkti kitų raktų zondavimo seka

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