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 veikia principu „paskutinis įėjo – pirmas išėjo“ (LIFO)?

  1. AEilė
  2. BMaišos lentelė
  3. CSusietasis sąrašas
  4. DStekas
2.Lengvas

Kas medyje yra broliniai (sibling) mazgai?

  1. AMazgai, turintys tą patį tėvą
  2. BMazgas ir jo tėvas
  3. CMazgai, neturintys vaikų
  4. DTame pačiame gylyje esantys skirtingų pomedžių mazgai
3.Lengvas

Kas yra medžio šaknis?

  1. AViršutinis mazgas, neturintis tėvo
  2. BMazgas be vaikų
  3. CMazgas su didžiausia reikšme
  4. DBet kuris mazgas viduryje
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(n²)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
5.Vidutinis

Kiek mazgų turi tobulas dvejetainis medis, kurio aukštis h (aukštis skaičiuojamas briaunomis)?

  1. Ah2
  2. B2h
  3. C2h+1 − 1
  4. D2h + 1
6.Vidutinis

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

  1. AEsami raktai surikiuojami vietoje
  2. BIšskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  3. CSeniausi raktai pašalinami vietai atlaisvinti
  4. DĮ naują perpildos sąrašą lentelės gale perkeliami tik susidūrę raktai
7.Sunkus

Kurią tiesinio zondavimo problemą dvigubas maišymas (double hashing) daugiausia sumažina?

  1. AMaišos funkcijos poreikį
  2. BPirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
  3. CPoreikį saugoti raktus lentelėje
  4. DRakto reikšmės skaitymo O(n) kainą
8.Sunkus

Mazgas su dviem vaikais iš dvejetainio paieškos medžio paprastai šalinamas:

  1. APakeičiant jį in-order įpėdiniu (arba pirmtaku) ir pašalinant tą mazgą
  2. BSukeičiant jį su šaknimi
  3. CPerstatant po juo esantį pomedį iš naujo ir iš naujo įterpiant kiekvieną jame buvusį raktą
  4. DPašalinant visą pomedį

Atsakymai

  1. 1. D · Stekas
  2. 2. A · Mazgai, turintys tą patį tėvą
  3. 3. A · Viršutinis mazgas, neturintis tėvo
  4. 4. D · O(1)
  5. 5. C · 2h+1 − 1
  6. 6. B · Išskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  7. 7. B · Pirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
  8. 8. A · Pakeičiant jį in-order įpėdiniu (arba pirmtaku) ir pašalinant tą mazgą

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