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

Kas saugoma kiekvienai viršūnei grafą vaizduojant gretimumo sąrašais?

1. AV loginių reikšmių eilutė
2. BJos kaimyninių viršūnių sąrašas
3. CBendras grafo briaunų skaičius
4. DTrumpiausias kelias iki kiekvienos kitos viršūnės

Grafą sudaro:

1. AViršūnės (mazgai), sujungtos briaunomis
2. BTik šaknis ir lapai
3. CTik raktai ir maišos reikšmės
4. DEilutės ir stulpeliai

Kas yra svorinis grafas?

1. AGrafas, saugomas diske
2. BGrafas, kurio kai kurios viršūnės sunkesnės už kitas, nes turi daugiau briaunų
3. CGrafas, turintis daugiau briaunų nei viršūnių
4. DGrafas, kurio kiekviena briauna turi skaitinę reikšmę, pvz., kainą ar atstumą

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

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

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

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

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. BStekas
3. CSubalansuotas dvejetainis paieškos medis
4. DMaišos lentelė

Kokią garantiją raudonai juodo medžio taisyklės suteikia medžio su n raktų aukščiui?

1. AAukštis ne didesnis kaip 2 log₂(n + 1)
2. BAukštis lygiai log₂ n
3. CAukštis ne didesnis kaip log₂ n + 1
4. DAukštis ne didesnis kaip n / 2

Struktūros union-find (nesikertančios aibės) su jungimu pagal rangą ir kelio suspaudimu amortizuota vienos operacijos kaina yra:

1. ATiksliai O(log n)
2. BO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
3. CO(n²)
4. DO(n)