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. ALaikas, reikalingas lentelei įkelti iš disko
  2. BIki šiol įvykusių kolizijų skaičius
  3. CKibirų skaičius, padalytas iš vidutinio saugomų raktų ilgio
  4. DSaugomų elementų skaičius, padalytas iš kibirų skaičiaus
2.Lengvas

Koks pagrindinis skirtumas tarp statinio ir dinaminio masyvo?

  1. AStatinis masyvas leidžia lėtesnę prieigą pagal indeksą
  2. BDinaminis masyvas gali augti persikeldamas į didesnį atminties bloką
  3. CDinaminis masyvas saugo elementus susietuose mazguose, kad galėtų augti po vieną
  4. DStatinis masyvas gali saugoti tik skaičius
3.Lengvas

Kuri struktūra paprastai naudojama prioritetinei eilei įgyvendinti?

  1. AStekas
  2. BNesutvarkytas vienkryptis susietasis sąrašas
  3. CKrūva
  4. DEilutė
4.Vidutinis

Kur yra mazgo su indeksu i tėvas dvejetainėje krūvoje, saugomoje masyve nuo indekso 0?

  1. AIndeksu ⌊i / 2⌋ + 1
  2. BIndeksu ⌊(i − 1) / 2⌋
  3. CIndeksu i − 1
  4. DIndeksu 2i + 1
5.Vidutinis

Kas nutinka, kai maišos lentelė, jos užpildymo koeficientui viršijus slenkstį, atlieka pakartotinį maišymą (rehash)?

  1. AIšskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  2. BEsami raktai surikiuojami vietoje
  3. CSeniausi raktai pašalinami vietai atlaisvinti
  4. DĮ naują perpildos sąrašą lentelės gale perkeliami tik susidūrę raktai
6.Vidutinis

Kokią balanso sąlygą AVL medis palaiko kiekviename mazge?

  1. AVisi lapai lygiai tame pačiame gylyje
  2. BKiekvienas mazgas nuspalvintas raudonai arba juodai
  3. CAbiejuose kiekvieno mazgo pomedžiuose yra lygiai tiek pat mazgų
  4. DKairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1
7.Sunkus

Operacijos decrease-key dvejetainėje krūvoje (žinant elemento poziciją) laiko sudėtingumas yra:

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

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

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

Atsakymai

  1. 1. D · Saugomų elementų skaičius, padalytas iš kibirų skaičiaus
  2. 2. B · Dinaminis masyvas gali augti persikeldamas į didesnį atminties bloką
  3. 3. C · Krūva
  4. 4. B · Indeksu ⌊(i − 1) / 2⌋
  5. 5. A · Išskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  6. 6. D · Kairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1
  7. 7. A · O(log n)
  8. 8. B · 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.