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

Koks pagrindinis skirtumas tarp statinio ir dinaminio masyvo?

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

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

1. AEilė
2. BMaišos lentelė
3. CStekas
4. DSusietasis sąrašas

Kiek briaunų turi medis su n mazgų?

1. An + 1
2. B2n
3. Cn
4. Dn − 1

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(n)
3. CO(1)
4. DO(log n)

Koks yra blogiausio atvejo dvejetainio paieškos medžio su n mazgų aukštis, jei raktai įterpiami surikiuota tvarka?

1. A√n
2. Bn (medis tampa susietuoju sąrašu)
3. Clog₂ n
4. D1

Kodėl masyvo apėjimas praktikoje dažnai daug greitesnis nei tokio pat ilgio susietojo sąrašo apėjimas?

1. AMasyvo elementai išdėstyti vientisai, todėl gerai išnaudoja procesoriaus podėlį (cache)
2. BMasyvai reikšmėms palyginti naudoja mažiau instrukcijų
3. CSusietieji sąrašai visada saugo elementus diske
4. DMasyvo apėjimas iš viso yra O(1), o susietojo sąrašo – O(n)

Iš n skaičių srauto reikia išlaikyti k mažiausių reikšmių naudojant O(k) atminties. Kuris būdas veikia per O(n log k)?

1. AMin krūva, laikanti visas n reikšmių, iš kurios pabaigoje išimama k mažiausių
2. BPaskutinių k reikšmių FIFO eilė
3. Ck dydžio max krūva, kurios šaknis pakeičiama atėjus mažesnei reikšmei
4. DVisų n reikšmių surikiuotas masyvas

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

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