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

Kuo apibrėžiamas dvejetainis medis?

1. AKiekvienas mazgas turi lygiai du vaikus
2. BKiekvienas mazgas saugo dvejetainį skaičių
3. CKiekvienas mazgas turi daugiausia du vaikus
4. DMedis turi lygiai du lygmenis

Kuri struktūra paprastai naudojama prioritetinei eilei įgyvendinti?

1. ANesutvarkytas vienkryptis susietasis sąrašas
2. BKrūva
3. CEilutė
4. DStekas

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

1. AStekas
2. BEilė
3. CMaišos lentelė
4. DPrioritetinė eilė

Kokia sargybinio (fiktyvaus, sentinel) mazgo paskirtis susietajame sąraše?

1. ANeleisti sąrašui augti virš nustatyto didžiausio mazgų skaičiaus
2. BPadaryti sąrašą surikiuotą
3. CSupaprastinti kodą pašalinant specialiuosius atvejus pradžioje ar pabaigoje
4. DSaugoti elementų skaičių

Prefiksų medis (trie) ypač efektyvus:

1. AMatricų saugojimui
2. BTrumpiausių kelių paieškai
3. CSkaičių rikiavimui
4. DPrefiksų paieškai, pavyzdžiui, automatiniam užbaigimui

Kaip dvejetainėje min krūvoje veikia extract-min?

1. APašalinamas paskutinis masyvo elementas
2. BPašalinama šaknis, o visi elementai pastumiami viena vieta į kairę
3. CPaskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)
4. DNaujo minimumo ieškoma visuose lapuose

Kurias operacijas Fenwicko medis (binary indexed tree) n skaičių masyvui palaiko per O(log n)?

1. APrefiksų sumų užklausas ir vieno elemento atnaujinimus
2. BMedianos radimą per O(1)
3. CElementų įterpimą bet kurioje pozicijoje
4. DMasyvo rikiavimą ir dvejetainę paiešką

Kodėl serveris galėtų savo maišos funkciją atsitiktinai parinkti iš universaliosios šeimos?

1. AKad maišos lentelė būtų surikiuota
2. BKad nebereikėtų keisti lentelės dydžio
3. CKad būtų labai mažai tikėtina, jog užpuolikas parinks daug raktų, kurie visi susiduria
4. DKad garantuotų, jog jokie du raktai niekada nesusidurs, kokius raktus beišsiųstų užpuolikas