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ą saugo atvaizdis (žodynas, map)?

  1. ATik reikšmes įterpimo tvarka
  2. BVienodų raktų poras
  3. CRaktų ir reikšmių poras su unikaliais raktais
  4. DPagal dydį surikiuotas reikšmes
2.Lengvas

Kuri duomenų struktūra labiausiai tinka teksto redaktoriaus funkcijai „atšaukti“ (undo)?

  1. AMaišos aibė
  2. BEilė
  3. CStekas
  4. DGrafas
3.Lengvas

Ką turi kiekvienas dvikrypčio susietojo sąrašo mazgas?

  1. ADvi duomenų kopijas ir vieną rodyklę
  2. BDuomenis, rodyklę į kitą mazgą ir rodyklę į ankstesnį mazgą
  3. CDuomenis ir dvi rodykles: vieną į kitą mazgą, o kitą į mazgą po jo
  4. DTik duomenis ir rodyklę į kitą mazgą
4.Vidutinis

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

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

AVL medžiai ir raudonai juodi medžiai garantuoja:

  1. APastovaus laiko paiešką bet kokiu atveju
  2. BKad nė vienas mazgas neturi dviejų vaikų
  3. CKad raktai saugomi įterpimo tvarka
  4. DO(log n) aukštį perbalansavimo dėka
6.Vidutinis

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

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

Kaip naudojant O(1) papildomos atminties nustatyti, ar vienkrypčiame susietajame sąraše yra ciklas?

  1. ASkaičiuoti mazgus, kol skaičius viršys sąrašo ilgio lauką
  2. BKiekvieną aplankytą mazgą saugoti maišos aibėje
  3. CVieną rodyklę stumti vienu žingsniu, kitą – dviem ir tikrinti, ar jos susitinka
  4. DSurikiuoti sąrašą ir ieškoti pasikartojimų
8.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. ANes atminties paskirstytuvas gali atlaisvinti atmintį tik bloko ketvirtadaliais
  2. BKad masyvas liktų surikiuotas
  3. CKad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
  4. DNes perpus mažinant esant pusei talpos būtų prarasti elementai

Atsakymai

  1. 1. C · Raktų ir reikšmių poras su unikaliais raktais
  2. 2. C · Stekas
  3. 3. B · Duomenis, rodyklę į kitą mazgą ir rodyklę į ankstesnį mazgą
  4. 4. C · Padedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę
  5. 5. D · O(log n) aukštį perbalansavimo dėka
  6. 6. A · O(V²)
  7. 7. C · Vieną rodyklę stumti vienu žingsniu, kitą – dviem ir tikrinti, ar jos susitinka
  8. 8. C · Kad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos

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