Užduočių lapas tema Duomenų struktūros su atsakymais

Koks pagrindinis skirtumas tarp statinio ir dinaminio masyvo?

1. AStatinis masyvas gali saugoti tik skaičius
2. BDinaminis masyvas gali augti persikeldamas į didesnį atminties bloką
3. CStatinis masyvas leidžia lėtesnę prieigą pagal indeksą
4. DDinaminis masyvas saugo elementus susietuose mazguose, kad galėtų augti po vieną

Kas yra medžio šaknis?

1. ABet kuris mazgas viduryje
2. BMazgas be vaikų
3. CViršutinis mazgas, neturintis tėvo
4. DMazgas su didžiausia reikšme

Kuri operacija masyvui yra O(1), o vienkrypčiam susietajam sąrašui – O(n)?

1. APirmojo elemento skaitymas
2. BĮterpimas į pradžią
3. CPrieiga prie elemento su indeksu i
4. DPirmojo elemento pašalinimas

Koks didžiausias galimas užpildymo koeficientas maišos lentelėje su atviruoju adresavimu?

1. A1
2. B2
3. CDidžiausio nėra
4. D0,5

Dvejetainio paieškos medžio apėjimas in-order aplanko raktus:

1. AĮterpimo tvarka
2. BDidėjančia (surikiuota) tvarka
3. CVisada mažėjančia tvarka
4. DLygmenų tvarka

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. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D1 2 4 5 3

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

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

Kaip naudojant O(1) papildomos atminties nustatyti, ar vienkrypčiame susietajame sąraše yra ciklas?

1. ASkaičiuoti mazgus, kol skaičius viršys sąrašo ilgio lauką
2. BSurikiuoti sąrašą ir ieškoti pasikartojimų
3. CVieną rodyklę stumti vienu žingsniu, kitą – dviem ir tikrinti, ar jos susitinka
4. DKiekvieną aplankytą mazgą saugoti maišos aibėje