Udajovky2

1. Log n operacie

vloz 23 strom

vymaz AVl

hladaj splay

vymaz rb

vymaz treap

vymaz 24

Submit

2. Pre súbor s priamym prístupom platí:

Je pomalý (nevhodný) ak chceme vždy spracovať všetky záznamy.

Umožňuje pristupovať k ľubovoľnému bloku v súbore.

V jednom bloku môže byť najviac 64 záznamov.

Option4

Submit

3. pre staicky hesovaci subor plati

jeden blok moze mat niekolko zaznamov

hesovacia funkcia mapuje kluc do oblasti adries blokov

subor je neutriedeny

Submit

4. Pre k-d strom platí:

Podporuje viacrozmerné intervalové vyh¾adávanie

Podporuje viacrozmerné bodové vyh¾adávanie

Pomocou rotácii sa dosahuje aspoò èiastoèná vyváenos

Je to modifikácia 2-3 stromu na binárny tvar

Podporuje operáciu zruenia (vymazania) prvku zo truktúry.

Ide o modifikáciu binárneho vyh¾adávacieho stromu

Submit

5. Pre AVL-strom platí:

. Jeho výška je najviac 1.44–násobkom výšky dokonale vyváženého stromu.

. Prvok, ktorý bol vyhľadaný sa pomocou rotácií dostane do koreňa stromu.

. Pri špecifickom poradí vkladaných prvkov môže degenerovať na lineárny zoznam.

. Teoretická zložitosť nájdenia ľubovoľného prvku je rovnaká ako pri binárnom vyhľadávacom strome.

. prehliadka inorder aplikovaná na Avl strom umožní výpis prvkov vzostupne usporiadaných podľa hodnoty kľúča.

. Dĺžka cesty z koreňa do každého z listov je rovnáka.

Submit

6. pre subor s priamym pristupom plati

Umoznuje pristupovat k lubovolnemu bloku v subore

v jednom bloku je max 64 zaznamov

dnes sa uz nevyzuiva

Option4

7. 23 strom

obsahuje iba unikatne kluce

zovseobecnenie RB stromu

zovseobecnenie 24 stromu

je to Binarny strom

delete je log(n)

naposledy vlozeny prvok je v koreni

Submit

8. Pre dynamické heovanie platí:

Vdy aktuálne pouíva pár heovacích funkcií (prístup ku kadému bloku je pomocou jednej z nich).

Jeho súèasou je aj index v tvare binárneho znakového stromu uloený v operaènej pamäti.

Bloky dát v súbore sú utriedené pod¾a k¾úèa.

Ide o kombináciu klasického heovacieho súboru a indexu (trie).

Rieenie kolízií je moné pomocou uzavretého adresovania.

Na zväèenie adresovacieho priestoru vyuíva zmenu heovacej funkcie.

Submit

9. Pre znakovy strom trie plati

pri vkladani sa vyuziva pridelenie nahodnej priority k prvku

kluc musi byt efektivne rozlozitelny na znaky

jeho modifikaciou je specialny strom De La Briandis strom

dlzka cesty z korena do listov je rovnaka

vkladany prvok sa dostane do pomocu rotacii do korena stromu

je modifikaciou 24 stromu ktora umoznuje vyhldavat kluc rozlozitelny na znaky

Submit

10. Pre RB-strom platí:

. Prvky, ku ktorým sa pristupuje najčastejšie sa nachádzajú bližšie pri koreni stromu.

. Je modifikáciou 2-4 stromu na binárny tvar.

. Je modifikáciou 2-3 stromu na binárny tvar.

. Koreň je vždy červený.

. Koreň je vždy čierny.

. Umožňuje vyhľadávať rovnako ako binárny vyhľadávací strom.

Submit

11. Pre skip list plati

Okrem hlavnej datovej struktury obsahuje pomocnu datovu strkuturu

vlozenie je o(1)

modifikacia splay

pouziva haldu

modifikacia 23 stromu

princip viac cestneho stromu

12. Pre sekvencny subor plati

pre zrychlenie pristupu je mozne vyuzit anticipovane citanie

vyuziva sa pri imlementacii linearneho hesovania

je pomaly,nevhodny, ak chceme spracovat vsetky zaznamy

zaznamy nemusia mat definovanu klucovu polozku (neda sa vyuzit pre pristup)

Zaznamy su vzdy utriedene podla hodnoty kluca

bloky mozu byt alokovane v nesuvislej oblasti - bloky zretazene adresami blokov (mozne na disku)

Submit

13. Pre operaciu splay v splay strome plati

Konci ked vrchol nad ktorym bola volana je list

zlozitost je n log n

konci ked vrchol nad ktorym bola voalan je na spravnom mieste podla nahodnej priority

konci ked vrchol nad ktorym bola volana je koren stromu

nepouziva rotacie,namiesto nich sa vyuziva zamena dvoch vrcholov

zlozitost je log n

Submit

14. Pre sekvenčný súbor platí:

Pre zrýchlenie prístupu je možné využiť anticipované čítanie.

Využíva sa pri implementácii lineárneho hešovania.

Je pomalý (nevhodný) ak chceme vždy spracovať všetky záznamy.

Záznamy nemusia mať definovanú kľúčovú položku (nedá sa využiť pre prístup).

Záznamy sú vždy utriedené podľa hodnoty kľúča.

Bloky môžu byť alokované v nesúvislej oblasti – bloky zreťazené adresami blokov (možné na disku).

Submit

15. Pre dynamické hešovanie platí:

Vždy aktuálne používa pár hešovacích funkcií (prístup ku každému bloku je pomocou jednej z nich).

Riešenie kolízií je možné pomocou uzavretého adresovania.

Ide o kombináciu klasického hešovacieho súboru a indexu (trie).

Bloky dát v súbore sú utriedené podľa kľúča.

Jeho súčasťou je aj index v tvare binárneho znakového stromu uložený v operačnej pamäti.

Na zväčšenie adresovacieho priestoru využíva zmenu hešovacej funkcie. (linearne heshovanie)

Submit

16. Pre statický hešovací súbor platí:

Pri tomto type hešovania nevznikajú preplňovacie bloky.

Vždy aktuálne používa pár hešovacích funkcií (prístup ku každému bloku je pomocou jednej z nich).

Hešovacia funkcia mapuje kľúč do oblasti adries blokov.

Jeden blok môže obsahovať niekoľko záznamov.

Jeho súčasťou je aj index v tvare binárneho znakového stromu-trie uložený v operačnej pamäti.

Súbor je neutriedený.

Submit

17. Pre truktúru Heap na disku platí:

Je to utriedený súbor s priamym prístupom.

Umoòuje rýchle a efektívne vyh¾adávanie.

Záznamy sú usporiadané pod¾a hodnoty k¾úèa.

Podporuje viacrozmerné bodové vyh¾adávanie.

Je to implicitná neutriedená tabu¾ka na disku.

Ide o modifikáciu binárneho vyh¾adávacieho stromu.

18. Pre dynamicke hesovanie plati

vzdy aktualne pouziva par hesovacich funkcii

riesenie kolizii je monze pomocou uzavreteho adresovania

ide o kombinaciu klasickeho hesovacie suboru a indexu trie

bloky dat su v subore usporiadane podla kluca

jeho sucastou je aj index v tvare binarneho znakoveho stromu ulozeny v operacnej pamati

na zvacsenie adresovacieho priestoru vyuziva zmenu hesovaecj funkcie

Submit

19. Riešenie kolízií v dynamickom hešovacom súbore je možné pomocou:

Otvoreného adresovania.

Súboru s preplňovacími blokmi.

Kolízie sú riešené rozdelením bloku, ktorý sa preplní.

Oblasti preplnenia blokov.

Oblasti preplnenia súboru.

Submit

20. Pre párovaciu haldu platí:

Je implementáciou prioritného frontu.

Je modifikáciou 2-4 stromu na binárny tvar.

Umožňuje vyhľadávať rovnako ako binárny vyhľadávací strom.

Operácia vloženia prvku má zložitosť O(1).

yhľadanie ľubovoľného prvku má zložitosť log ( n ).

not sure

Explanation

not sure

Submit

21. Pre heap plati

Je to implicitna neutriedena tabulka na disku

je to utriedeny subor s priamym pristupom

umoznuje rychle a efektivne vyhladavanie

Option4

22. Pre staticky hashovaci plati

subor je neutriedeny

pri tomto type hesovania nevznikaju preplnovacie bloky

jeho sucastou je aj index v tvare binarneho znakoveho stromu trie ulozeny v operacnej pamati

hesovacia funkcia mapuje kluc do oblasti adries blokov

jeden blok moze obsahovat niekolko zaznamov

vzdy aktualne pouziva par hesovacich funkcii

Submit

23. Riešenie kolízií v lineárnom hešovacom súbore je možné pomocou:

Súboru s preplňovacími blokmi.

Pri tomto type hešovania nevznikajú kolízie.

Uzavretého adresovania.

Oblasti preplnenia blokov.

Otvoreného adresovania.

Nepriameho adresovania.

Submit

24. Pre každý vrchol (prvok) Treap stromu platí:

Každý prvok obsahuje kľuč, ktorý je v celom strome jedinečný (unikátny).

Prvok stromu je charakterizovaný kľúčom a prioritou.

Prvok stromu je charakterizovaný iba kľučom, ktorý nazývame priorita.

Prvok s najvyššou prioritou sa nachádza v koreni stromu.

Inorder nasledovník prvku má vždy nižšiu prioritu.

Na základe hodnoty kľúča je prvku pridelená priorita, ktorá je výsledkom hash funkcie aplikovanej na kľuč.

Submit

25. pre subor s priamym pristupom plati

je pomaly, nevhodny ak chceme spracovat vsetky zaznamy

umoznuje pristupovat k lubovolnemu bloku v subore

v jednom bloku je max 64 zaznamov

26. Pre rozšíriteľný hešovací súbor platí:

Bloky dát v súbore sú utriedené podľa kľúča.

Ide o kombináciu klasického hešovacieho súboru a indexu v tvare trie. (dynamicke heshovanie)

Na zväčšenie adresovacieho priestoru využíva zmenu hešovacej funkcie. (linearne heshovanie)

Na určenie adresy bloku sa používa adresár uložený v operačnej pamäti.

Vždy aktuálne používa pár hešovacích funkcií (prístup ku každému bloku je pomocou jednej z nich).

Jeden blok v súbore môže mať najviac 32 záznamov.

27. Pre lineárny hešovací súbor platí:

Vždy aktuálne používa pár hešovacích funkcií (prístup k všetkým blokom je pomocou jednej z nich).

Využíva indexovú štruktúru pre prístup k blokom.

Pri tomto type hešovania nevznikajú preplňovacie bloky. (pouziva preplnovacie bloky)

Option4

28. Pre rozírite¾ný heovací súbor platí:

Bloky dát v súbore sú utriedené pod¾a k¾úèa.

Ide o kombináciu klasického heovacieho súboru a indexu v tvare trie.

Na zväèenie adresovacieho priestoru vyuíva zmenu heovacej funkcie.

Na urèenie adresy bloku sa pouíva adresár uloený v operaènej pamäti.

Vdy aktuálne pouíva pár heovacích funkcií (prístup ku kadému bloku je pomocou jednej z nich).

Jeden blok v súbore môe obsahova najviac 32 záznamov.

29. Pre Splay-strom platí:

a. Dĺžka cesty z koreňa do každého z listov je rovnaká.

b. Využíva princíp binárnej haldy (prvky sú haldovo usporiadané).

c. Prvok, ktorý bol vyhľadaný sa pomocou rotácií dostane do koreňa stromu.

d. Zmazanie prvku s najmenším kľúčom má zložitosť O(1).

e. Teoretická zložitosť nájdenia ľubovoľného prvku je rovnaká ako pri binárnom vyhľadávacom strome.

f. Prehliadka preorder aplikovaná na Splay strom umožní výpis prvkov vzostupne usporiadaných podľa hodnoty kľúča.

Submit

30. RB

je modifikacia 24 stromu na binarny tvar

najdi je o(n)

koren je cerveny

prehliadka inorder umozni vypis prvkov podla hodnoty kluca

dlzka cesty z korena do kazdeho listu je rovnaka

prvok ktory bol vyhladany sa pomomcou rotacii dostane do korena stromu

Submit

31. Označte operácie, ktorých teoretická zložitosť je log(n):

a. Inorder prehliadka AVL stromu.

b. Zmazanie prvku v štruktúre Treap.

c. Vloženie prvku do Fibonacciho haldy.

d. Vyhľadanie prvku v 2-3 strome.

e. Vyhľadanie prvku v párovacej halde.

f. Vyhľadanie prvku v RB strome.

a. Inorder prehliadka AVL stromu. N
c. Vloženie prvku do Fibonacciho haldy.log 1

Explanation

a. Inorder prehliadka AVL stromu. N
c. Vloženie prvku do Fibonacciho haldy.log 1

Submit

32. Pre B+ strom platí:

Na implementáciu sa použije súbor s priamym prístupom .

Pri špecifickom poradí mazaných prvkov môže degenerovať na lineárny zoznam.

Skladá sa z indexu implementovaného pomocou štruktúry Trie (digitálny znakový strom) a dát na disku.

Index sa nachádza v operačnej pamäti.

Skladá sa z indexu v tvare R-B-stromu a dát, ktoré sú uložené v utriedenom súbore.

Skladá sa z indexu v tvare B-stromu a dát, ktoré sú uložené v utriedenom súbore.

nie som si isty

Explanation

nie som si isty

Submit

33. Pre skip list platí:

. Pozostáva z množiny zoznamov.

. Okrem hlavnej (dátovej) štruktúry obsahujúcej prvky (záznamy) tabuľky obsahuje pomocnú dátovú truktúru.

. Je modifikáciou 2-4 stromu na binárny tvar.

Pri vkladaní využíva priradenie náhodnej priority k prvku.

34. Pre Quad plati

Podporuje dvojrozmerne bodove vyhladavanie

je to stvor cestny strom

podporuje trojrozmerne intrevaloe vyhladavanie

Option4

Submit

35. K D Strom plati

ide o modifikaciu BST

podporuje viacrozmerne bodove vyhladavannie

podporuje viacrozmerne intervalove vyhladavannie

Option4

Submit