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

Maišos lentelė (hash table) saugo duomenis kaip:

1. AMedį su sutvarkytais raktais
2. BTik surikiuotą sąrašą
3. CFiksuoto ilgio eilutę
4. DRakto ir reikšmės poras, randamas maišos funkcija

Mazgo gylis medyje yra:

1. ATo mazgo vaikų skaičius
2. BJo pomedžio mazgų skaičius
3. CBriaunų skaičius nuo šaknies iki to mazgo
4. DBriaunų skaičius nuo to mazgo iki giliausio lapo

Kas nekryptiniame grafe yra viršūnės laipsnis?

1. AGrafo viršūnių skaičius
2. BIlgiausio iš jos einančio kelio ilgis
3. CSu ja sujungtų briaunų skaičius
4. DJos pozicija gretimumo sąraše

Kaip naujas elementas įterpiamas į dvejetainę krūvą?

1. AVisa krūva perstatoma iš naujo
2. BPadedamas šaknyje ir leidžiamas žemyn
3. CĮterpiamas į surikiuotą poziciją, pastumiant visus didesnius elementus viena vieta į dešinę
4. DPadedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę

Kokia kaina įterpti elementą į n elementų masyvo vidurį?

1. AO(n²), nes kiekvienas elementas pajuda n kartų
2. BO(1), nes indeksas žinomas
3. CO(n), nes vėlesnius elementus reikia pastumti
4. DO(log n), dėl dvejetainės paieškos

Kaip rasti mažiausią raktą dvejetainiame paieškos medyje?

1. ANuo šaknies eiti dešiniaisiais vaikais, kol nebėra dešiniojo vaiko
2. BPažiūrėti tik į šaknį
3. CNuo šaknies eiti kairiaisiais vaikais, kol nebėra kairiojo vaiko
4. DAplankyti kiekvieną lapą ir juos palyginti

Dinaminis masyvas užsipildęs padvigubėja. Kodėl daugelis įgyvendinimų jį sumažina tik tada, kai jis užpildytas ketvirtadaliu, o ne perpus?

1. AKad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
2. BNes atminties paskirstytuvas gali atlaisvinti atmintį tik bloko ketvirtadaliais
3. CNes perpus mažinant esant pusei talpos būtų prarasti elementai
4. DKad masyvas liktų surikiuotas

Esant paprastam tolygiam maišymui, koks tikėtinas paieškos laikas maišos lentelėje su grandinėmis, n raktų ir m kibirų?

1. AO(log n)
2. BO(1 + α), kur α = n / m
3. CO(n)
4. DO(m)