Otazky_and_Odpovedi

nize. Narocnejsi, setri místo - v kombinaci se stromovou strukturou pouziti u B+ stromu

9. Při přenosu zpráv kódovaných prvky abecedy {a, b, c, d} se vyskytují prvky této abecedy s pravděpodobnostmi {0,6 0,2 0,1 0,1} odvoďte binární ekvivalenty těchto prvků a zapište kód zpráv abba dad a baba (str. 94)
- analogie Shanon-fanova a Hufmanova kodovani
a – 0,61
b – 0,201
c – 0,1000
d – 0,1001
abba – 101011
dad – 0011001
a – 1
baba – 011011
10. Ilustrujte a vysvětlete princip přidělování paměti souborů na disku na bázi mapy disku. (str. 24)
- Vychazi z principu FAT tabulky
- Tabulka, kde se uchovava fyzicka pozice zacatku souboru na disku a nasledne bloky, ve kterych je soubor ulozen = soubor nemusi na disku zabirat souvisly prostor, jeho pozice je svazana ve FAT pomoci ukazatelu
- Problem vnitrni fragmentace souboru
- Vhodny při pouziti alokacnich bloku s malou delkou
- Efektivni při pouziti disku do 0,5 GB, blok do velikosti 8KB
11. Vysvětlete princip vedení přehledu o volných alokačních blocích řetězením volných alokačních bloků a uveďte základní vlastnosti této metody (str. 25)
- Volne bloky obsahuji ukazatele na nejblizzi nasledujici volne bloky = snadna imlementace
- Obtizne se hleda vetsi souvisly prostor
- Další moznost retezeni skupin volnych fyzickych stranek = snadnejsi hledani souvisleho volneho prostoru
12. Uveďte vlastnosti listu B+ stromu (str. 78…)
- List může obsahovat 1…m-1 záznamů
- Všechny listy dohromady obsahuji všechny zaznamy uchovavane ve strome, které jsou navic vzestupne setridene
- Poslední ukazatel listu ukazuje na počáteční ukazatel příštího listu = je umožneno sekvencni prohledavani všech zaznamu stromu na listove urovni
13. Uveďte vlastnosti m-árního vyhledávacího stromu (str. 71…)
- m>2
- M klicu v uzlu = M+1 podstromu
- Každý podstrom ma hodnoty klicu mezi hodnotami 2 sousednich hodnot v klici z neho vychazi = kombinace s indexovym vyhledavanim
- Snaha o snizeni hloubky stromu
- Hloubka h = log m (n+1) při vyvazenosti
14. Vysvetlete princip organizace indexovani souboru bitovou mapou (str. 50-54)
- Implementace hlavne a databazovych strukturach (SQL), pro zaznamy s malou domenou hodnot, které mají pevnou delku
- Dotazy = operace nad bitovymi vektory – pomoci jednoduchych Booleovskych operatoru
= existence, and, or, xor
- Bitove mapy – prostor radove % puvodni delky pevneho zaznamu
15. Uveďte rozdíl mezi struktrou adresáře typu "strom" a typu "acyklický graf" a charkterizujte potřebné vlastnosti operace rušení souboru v obou typech adresářů (str. 72-73).
- Acyklicky graf – méně prehledny pro praci se soubory
= jednoduchy graf s orientovnymi hranami, který neobsahuje cykly
Strom – jakasi podmnozina jednoduchemo grafu = neobsahuje smycky, cykly, hrany jsou orientovane, je souvisly a mezi uzly existuje max 1 hrana
- je prirozenejsi a prehlednejsi pro praci se soubory – při ruseni musime uvazovat a vyvazenosti, arite uzlu.. plati vztahy rodic … potomek
16. Co se rozumí pojmem "blokovací faktor" a ilustrujte jeho aplikaci na úrovni logické paměti a na úrovni fyzické paměti (str. 33).
- Cil, aby blok obsahoval celistvy počet zaznamu = počet zaznamu v bloku cele cislo
- Na logicke urovni = zvolit blokovaci faktor optimalne vzhledem k velikostem zaznamu a velikosti pameti, tak aby se usnadnila indexace a vyhledavani jednotlivych zaznamu, a aby se zkratil cas potrebny k vyhledavani
- Na fyzicke urovni = implementace a pridani oddelovacu logickeho navrhu primo na miru pouzitych typu pameti, medii, aby nevznikalo nevyu