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

Kas medyje yra lapas?

1. AMazgas su didžiausia reikšme
2. BMazgas, neturintis tėvo
3. CMazgas, turintis lygiai vieną vaiką
4. DMazgas, neturintis vaikų

Kuri struktūra paprastai naudojama prioritetinei eilei įgyvendinti?

1. ANesutvarkytas vienkryptis susietasis sąrašas
2. BStekas
3. CKrūva
4. DEilutė

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

1. ABendras grafo briaunų skaičius
2. BV loginių reikšmių eilutė
3. CTrumpiausias kelias iki kiekvienos kitos viršūnės
4. DJos kaimyninių viršūnių sąrašas

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

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

Dvejetainio medžio šaknis yra 1, jos kairysis vaikas 2, dešinysis 3; mazgas 2 turi vaikus 4 (kairįjį) ir 5 (dešinįjį). Koks preorder apėjimas?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

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

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

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

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

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²)
3. CO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
4. DO(n)