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. CTik duomenis
  4. DDuomenis ir nuorodas į visus kitus mazgus
2.Lengvas

Kas yra medžio šaknis?

  1. AMazgas be vaikų
  2. BViršutinis mazgas, neturintis tėvo
  3. CMazgas su didžiausia reikšme
  4. DBet kuris mazgas viduryje
3.Lengvas

Kuri operacija masyve lėta, bet susietojo sąrašo pradžioje greita?

  1. AFiksuoto masyvo ilgio nustatymas
  2. BĮterpimas į pradžią
  3. CPrieiga prie 5-ojo elemento
  4. DPaskutinio elemento skaitymas pagal indeksą
4.Vidutinis

Eilė įgyvendinta dviem stekais: push atliekamas į steką „in“, o pop – iš steko „out“, kuris, ištuštėjęs, papildomas iš „in“. Kokia amortizuota vienos operacijos kaina?

  1. AO(log n)
  2. BO(n²)
  3. CO(1)
  4. DO(n)
5.Vidutinis

Kokia sargybinio (fiktyvaus, sentinel) mazgo paskirtis susietajame sąraše?

  1. ASaugoti elementų skaičių
  2. BNeleisti sąrašui augti virš nustatyto didžiausio mazgų skaičiaus
  3. CPadaryti sąrašą surikiuotą
  4. DSupaprastinti kodą pašalinant specialiuosius atvejus pradžioje ar pabaigoje
6.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 preorder apėjimas?

  1. A1 2 3 4 5
  2. B1 2 4 5 3
  3. C4 5 2 3 1
  4. D4 2 5 1 3
7.Sunkus

Kurias operacijas Fenwicko medis (binary indexed tree) n skaičių masyvui palaiko per O(log n)?

  1. AMedianos radimą per O(1)
  2. BMasyvo rikiavimą ir dvejetainę paiešką
  3. CPrefiksų sumų užklausas ir vieno elemento atnaujinimus
  4. DElementų įterpimą bet kurioje pozicijoje
8.Sunkus

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

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

Atsakymai

  1. 1. B · Duomenis ir nuorodą į kitą mazgą
  2. 2. B · Viršutinis mazgas, neturintis tėvo
  3. 3. B · Įterpimas į pradžią
  4. 4. C · O(1)
  5. 5. D · Supaprastinti kodą pašalinant specialiuosius atvejus pradžioje ar pabaigoje
  6. 6. B · 1 2 4 5 3
  7. 7. C · Prefiksų sumų užklausas ir vieno elemento atnaujinimus
  8. 8. C · O(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi

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