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

Vienkrypčiame susietajame sąraše kiekvienas mazgas turi:

  1. ADuomenis ir indeksą
  2. BDuomenis ir nuorodą į kitą mazgą
  3. CDuomenis ir nuorodas į visus kitus mazgus
  4. DTik duomenis
2.Lengvas

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

  1. AMedį su sutvarkytais raktais
  2. BFiksuoto ilgio eilutę
  3. CRakto ir reikšmės poras, randamas maišos funkcija
  4. DTik surikiuotą sąrašą
3.Lengvas

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

  1. AJos pozicija gretimumo sąraše
  2. BGrafo viršūnių skaičius
  3. CSu ja sujungtų briaunų skaičius
  4. DIlgiausio iš jos einančio kelio ilgis
4.Vidutinis

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

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

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

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

Kiek laiko užtrunka L ilgio žodžio paieška Trie medyje su fiksuota abėcėle?

  1. AO(n), kur n yra žodžių skaičius
  2. BO(L × n)
  3. CO(log n), kur n yra žodžių skaičius
  4. DO(L), nepriklausomai nuo saugomų žodžių skaičiaus
7.Sunkus

Dinaminis masyvas užsipildęs padvigubėja. Kodėl daugelis įgyvendinimų jį sumažina tik tada, kai jis užpildytas ketvirtadaliu, o ne perpus?

  1. AKad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
  2. BKad masyvas liktų surikiuotas
  3. CNes perpus mažinant esant pusei talpos būtų prarasti elementai
  4. DNes atminties paskirstytuvas gali atlaisvinti atmintį tik bloko ketvirtadaliais
8.Sunkus

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

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

Atsakymai

  1. 1. B · Duomenis ir nuorodą į kitą mazgą
  2. 2. C · Rakto ir reikšmės poras, randamas maišos funkcija
  3. 3. C · Su ja sujungtų briaunų skaičius
  4. 4. D · Paskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  5. 5. C · Indeksu ⌊(i − 1) / 2⌋
  6. 6. D · O(L), nepriklausomai nuo saugomų žodžių skaičiaus
  7. 7. A · Kad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
  8. 8. D · 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.