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

Kiek briaunų turi medis su n mazgų?

  1. An + 1
  2. Bn
  3. Cn − 1
  4. D2n
2.Lengvas

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

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

Dvejetainiame paieškos medyje mazgo kairiojo pomedžio reikšmės yra:

  1. AMažesnės už mazgo reikšmę
  2. BLygios mazgo reikšmei
  3. CAtsitiktine tvarka
  4. DDidesnės už mazgo reikšmę
4.Vidutinis

Kodėl dvejetainę krūvą galima saugoti masyve be jokių rodyklių?

  1. AKrūvose niekada nebūna daugiau kaip 100 elementų
  2. BMasyvai automatiškai laiko raktus surikiuotus, todėl rodyklių nereikia
  3. CVisi krūvos raktai lygūs
  4. DTai pilnas dvejetainis medis, todėl pozicijas nusako paprastos indeksų formulės
5.Vidutinis

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

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

Kokia rakto paieškos subalansuotame dvejetainiame paieškos medyje laiko sudėtingumas?

  1. AO(n)
  2. BO(n log n)
  3. CO(1)
  4. DO(log n)
7.Sunkus

Kodėl maišos lentelėje su atviruoju adresavimu šalinimas dažnai atliekamas naudojant „antkapio“ (tombstone) žymę?

  1. AIštuštinus vietą, galėtų nutrūkti kitų raktų zondavimo seka
  2. BDėl to lentelė tampa surikiuota
  3. CAntkapiai pagreitina maišymą
  4. DPašalinti raktai saugumo sumetimais turi būti laikomi amžinai, todėl vietų niekada negalima naudoti pakartotinai
8.Sunkus

Kokia blogiausio atvejo vienos find operacijos kaina union-find struktūroje su n elementų, nenaudojant jungimo pagal rangą ir kelio suspaudimo?

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(α(n))

Atsakymai

  1. 1. C · n − 1
  2. 2. A · Stekas
  3. 3. A · Mažesnės už mazgo reikšmę
  4. 4. D · Tai pilnas dvejetainis medis, todėl pozicijas nusako paprastos indeksų formulės
  5. 5. D · O(log n) aukštį perbalansavimo dėka
  6. 6. D · O(log n)
  7. 7. A · Ištuštinus vietą, galėtų nutrūkti kitų raktų zondavimo seka
  8. 8. A · O(n)

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