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

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

1. ADvejetainis medis
2. BStekas
3. CEilė
4. DKrūva

Kas yra maišos lentelės užpildymo koeficientas (load factor)?

1. AKibirų skaičius, padalytas iš vidutinio saugomų raktų ilgio
2. BIki šiol įvykusių kolizijų skaičius
3. CLaikas, reikalingas lentelei įkelti iš disko
4. DSaugomų elementų skaičius, padalytas iš kibirų skaičiaus

Dvejetainiame paieškos medyje mazgo kairiojo pomedžio reikšmės yra:

1. AAtsitiktine tvarka
2. BDidesnės už mazgo reikšmę
3. CLygios mazgo reikšmei
4. DMažesnės už mazgo reikšmę

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

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

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

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

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

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

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

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

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

1. AMedianos radimą per O(1)
2. BMasyvo rikiavimą ir dvejetainę paiešką
3. CPrefiksų sumų užklausas ir vieno elemento atnaujinimus
4. DElementų įterpimą bet kurioje pozicijoje