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

Kuri operacija masyve lėta, bet susietojo sąrašo pradžioje greita?

1. APrieiga prie 5-ojo elemento
2. BFiksuoto masyvo ilgio nustatymas
3. CĮterpimas į pradžią
4. DPaskutinio elemento skaitymas pagal indeksą

Kas medyje yra broliniai (sibling) mazgai?

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

Kuri duomenų struktūra naudojama medžio apėjimui lygmenimis (level-order)?

1. AMaišos lentelė
2. BPrioritetinė eilė
3. CStekas
4. DEilė

Kiek atminties naudoja grafo su V viršūnių gretimumo matrica?

1. AO(E)
2. BO(V²)
3. CO(V + E)
4. DO(log V)

Programai reikia greitos paieškos, taip pat reikia išvardyti raktus surikiuota tvarka ir atsakyti į intervalų užklausas. Kuri struktūra tinka geriausiai?

1. ANesurikiuotas susietasis sąrašas
2. BSubalansuotas dvejetainis paieškos medis
3. CMaišos lentelė
4. DStekas

Kas teisinga apie nekryptinio grafo gretimumo matricą?

1. AJi visada viršutinė trikampė
2. BJi simetriška pagrindinės įstrižainės atžvilgiu
3. CJos pagrindinėje įstrižainėje visada yra vienetai
4. DKiekvienoje eilutėje yra lygiai vienas 1

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. AVisų n reikšmių surikiuotas masyvas
2. Bk dydžio max krūva, kurios šaknis pakeičiama atėjus mažesnei reikšmei
3. CPaskutinių k reikšmių FIFO eilė
4. DMin krūva, laikanti visas n reikšmių, iš kurios pabaigoje išimama k mažiausių

Kiek laiko užtrunka bet kurio rakto paieška n elementų dvejetainėje min krūvoje?

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