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

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

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

Kas yra kryptinis grafas?

1. AGrafas, kurio briaunos turi kryptį iš vienos viršūnės į kitą
2. BGrafas, kurio visos briaunos turi svorius
3. CGrafas, kuriame kiekviena skirtingų viršūnių pora sujungta briauna
4. DGrafas, neturintis ciklų

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

1. APrioritetinė eilė
2. BEilė
3. CMaišos lentelė
4. DStekas

AVL medžiai ir raudonai juodi medžiai garantuoja:

1. AKad raktai saugomi įterpimo tvarka
2. BO(log n) aukštį perbalansavimo dėka
3. CPastovaus laiko paiešką bet kokiu atveju
4. DKad nė vienas mazgas neturi dviejų vaikų

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 postorder apėjimas?

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

Kuris kolizijų sprendimo metodas saugo susidūrusius raktus sąraše tame pačiame kibire?

1. AKvadratinis zondavimas
2. BDvigubas maišymas
3. CTiesinis zondavimas
4. DAtskiros grandinės (separate chaining)

Kodėl iš standartinio Bloomo filtro elementų negalima tiesiog pašalinti išvalant jų bitus?

1. ATie bitai gali priklausyti ir kitiems elementams, todėl atsirastų klaidingai neigiami atsakymai
2. BŠalinimas padidintų klaidingai teigiamų atsakymų dažnį iki 100%
3. CBloomo filtro bitų negalima keisti po sukūrimo
4. DBloomo filtrai saugo visus elementus, o suhešavus jų vėl neįmanoma rasti

Kurią tiesinio zondavimo problemą dvigubas maišymas (double hashing) daugiausia sumažina?

1. APirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
2. BPoreikį saugoti raktus lentelėje
3. CMaišos funkcijos poreikį
4. DRakto reikšmės skaitymo O(n) kainą