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

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

  1. AStekas
  2. BMaišos aibė
  3. CEilė
  4. DGrafas
2.Lengvas

Kas yra maišos lentelės užpildymo koeficientas (load factor)?

  1. AIki šiol įvykusių kolizijų skaičius
  2. BKibirų skaičius, padalytas iš vidutinio saugomų raktų ilgio
  3. CLaikas, reikalingas lentelei įkelti iš disko
  4. DSaugomų elementų skaičius, padalytas iš kibirų skaičiaus
3.Lengvas

Kuri duomenų struktūra veikia principu „pirmas įėjo – pirmas išėjo“ (FIFO)?

  1. ADvejetainis medis
  2. BKrūva
  3. CEilė
  4. DStekas
4.Vidutinis

Dvejetainio medžio šaknis yra 1, jos kairysis vaikas 2, dešinysis 3; mazgas 2 turi vaikus 4 (kairįjį) ir 5 (dešinįjį). Koks postorder apėjimas?

  1. A5 4 3 2 1
  2. B1 2 4 5 3
  3. C4 2 5 1 3
  4. D4 5 2 3 1
5.Vidutinis

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

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

Prefiksų medis (trie) ypač efektyvus:

  1. AMatricų saugojimui
  2. BPrefiksų paieškai, pavyzdžiui, automatiniam užbaigimui
  3. CSkaičių rikiavimui
  4. DTrumpiausių kelių paieškai
7.Sunkus

Struktūros union-find (nesikertančios aibės) su jungimu pagal rangą ir kelio suspaudimu amortizuota vienos operacijos kaina yra:

  1. AO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
  2. BTiksliai O(log n)
  3. CO(n²)
  4. DO(n)
8.Sunkus

Ką skleidžiamasis medis (splay tree) atlieka po kiekvienos prieigos?

  1. APerstato visą medį į subalansuotą formą
  2. BPerspalvina paieškos kelio mazgus
  3. CPerkelia pasiektą mazgą į lapą
  4. DPosūkiais iškelia pasiektą mazgą į šaknį

Atsakymai

  1. 1. A · Stekas
  2. 2. D · Saugomų elementų skaičius, padalytas iš kibirų skaičiaus
  3. 3. C · Eilė
  4. 4. D · 4 5 2 3 1
  5. 5. C · Paskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  6. 6. B · Prefiksų paieškai, pavyzdžiui, automatiniam užbaigimui
  7. 7. A · O(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
  8. 8. D · Posūkiais iškelia pasiektą mazgą į šaknį

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