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. ASusietasis sąrašas
  2. BMaišos lentelė
  3. CStekas
  4. DEilė
2.Lengvas

Kas yra medžio šaknis?

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

Medžio aukštis paprastai apibrėžiamas kaip:

  1. AMedžio lapų skaičius
  2. BŠaknies vaikų skaičius
  3. CBriaunų skaičius ilgiausiame kelyje nuo šaknies iki lapo
  4. DBendras medžio mazgų skaičius, skaičiuojant šaknį ir kiekvieną lapą
4.Vidutinis

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

  1. APaskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  2. BPašalinama šaknis, o visi elementai pastumiami viena vieta į kairę
  3. CPašalinamas paskutinis masyvo elementas
  4. DNaujo minimumo ieškoma visuose lapuose
5.Vidutinis

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

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

Kokią balanso sąlygą AVL medis palaiko kiekviename mazge?

  1. AKiekvienas mazgas nuspalvintas raudonai arba juodai
  2. BKairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1
  3. CVisi lapai lygiai tame pačiame gylyje
  4. DAbiejuose kiekvieno mazgo pomedžiuose yra lygiai tiek pat mazgų
7.Sunkus

Kuo radix medis (suspaustas Trie) pranašesnis už paprastą Trie?

  1. AJis išlaiko tik pirmąją kiekvieno žodžio raidę
  2. BJis kiekvieną žodį saugo šaknyje esančioje maišos lentelėje, o ne atskiruose mazguose
  3. CJis vieno vaiko mazgų grandines sujungia į vieną eilute pažymėtą briauną
  4. DJis kiekvieno mazgo vaikus surikiuoja pagal dažnį
8.Sunkus

Koks pagrindinis šuolių sąrašo (skip list) pranašumas prieš surikiuotą susietąjį sąrašą?

  1. AJis saugo raktus be tvarkos
  2. BGarantuota O(1) paieška, nes kiekvienas mazgas saugo rodyklę į kiekvieną kitą mazgą
  3. CJis nenaudoja papildomos atminties
  4. DTikėtina O(log n) paieška naudojant kelis į priekį rodančių rodyklių lygmenis

Atsakymai

  1. 1. C · Stekas
  2. 2. B · Viršutinis mazgas, neturintis tėvo
  3. 3. C · Briaunų skaičius ilgiausiame kelyje nuo šaknies iki lapo
  4. 4. A · Paskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
  5. 5. D · O(log n)
  6. 6. B · Kairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1
  7. 7. C · Jis vieno vaiko mazgų grandines sujungia į vieną eilute pažymėtą briauną
  8. 8. D · Tikėtina O(log n) paieška naudojant kelis į priekį rodančių rodyklių lygmenis

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