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ą maišos lentelėje atlieka maišos funkcija?

  1. ASurikiuoja lentelės raktus
  2. BSuskaičiuoja, kiek raktų saugoma
  3. CUžšifruoja lentelės reikšmes
  4. DSusieja raktą su lentelės indeksu
2.Lengvas

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

  1. ASu ja sujungtų briaunų skaičius
  2. BGrafo viršūnių skaičius
  3. CIlgiausio iš jos einančio kelio ilgis
  4. DJos pozicija gretimumo sąraše
3.Lengvas

Kuri struktūra paprastai naudojama prioritetinei eilei įgyvendinti?

  1. AEilutė
  2. BStekas
  3. CKrūva
  4. DNesutvarkytas vienkryptis susietasis sąrašas
4.Vidutinis

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

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

Kodėl masyvo apėjimas praktikoje dažnai daug greitesnis nei tokio pat ilgio susietojo sąrašo apėjimas?

  1. ASusietieji sąrašai visada saugo elementus diske
  2. BMasyvo elementai išdėstyti vientisai, todėl gerai išnaudoja procesoriaus podėlį (cache)
  3. CMasyvai reikšmėms palyginti naudoja mažiau instrukcijų
  4. DMasyvo apėjimas iš viso yra O(1), o susietojo sąrašo – O(n)
6.Vidutinis

Kas teisinga apie nekryptinio grafo gretimumo matricą?

  1. AKiekvienoje eilutėje yra lygiai vienas 1
  2. BJos pagrindinėje įstrižainėje visada yra vienetai
  3. CJi simetriška pagrindinės įstrižainės atžvilgiu
  4. DJi visada viršutinė trikampė
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 masyvas liktų surikiuotas
  2. BKad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
  3. CNes atminties paskirstytuvas gali atlaisvinti atmintį tik bloko ketvirtadaliais
  4. DNes perpus mažinant esant pusei talpos būtų prarasti elementai
8.Sunkus

Esant paprastam tolygiam maišymui, koks tikėtinas paieškos laikas maišos lentelėje su grandinėmis, n raktų ir m kibirų?

  1. AO(log n)
  2. BO(n)
  3. CO(m)
  4. DO(1 + α), kur α = n / m

Atsakymai

  1. 1. D · Susieja raktą su lentelės indeksu
  2. 2. A · Su ja sujungtų briaunų skaičius
  3. 3. C · Krūva
  4. 4. C · Išskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  5. 5. B · Masyvo elementai išdėstyti vientisai, todėl gerai išnaudoja procesoriaus podėlį (cache)
  6. 6. C · Ji simetriška pagrindinės įstrižainės atžvilgiu
  7. 7. B · Kad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
  8. 8. D · O(1 + α), kur α = n / m

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