Otazky_and_Odpovedi

zite místo v blocich, nebo aby zaznamy nebyly prerostle přes vice bloku
17. Je-li délka bloku vnější paměti B, průměrná délka klíče V a velikost ukazatele bloku vnější paměti P, kolik úrovní bude mít index index-sekvenčně organizovaného souboru s N záznamy bolkovanými s faktorem b (str 49).
- Delka bloku vnejsi pameti … B
- Prumerna delka klice … V
- Velikost ukazatelu do vnejsi pameti … P
- Počet urovni ??? … n
- N zaznamu
- b … blokovaci faktor
n = cela horni část (log p (N/b))
p = cela dolni část (B/(V+P))
18. Mohou být sekundární indexy indexově organizovaného souboru řídké? Odpověď zdůvodněte (str. 47).
- Sekundarni index musí byt husty
- Sek. Index se musí udrzovat synchrone s primarnim indexem
- Primarni + sekundarni index musí jednoznacne identifikovat zaznam
- Muze napr. ukazovat na kapsu, která obsahuje ukazatele na všechny zaznamy v primarnim souboru s jistou konkretni hodnotou sek. vyhledavaciho klice
- Sekundarni indexy odkazuji neprimo do primarniho souboru, přes primarni klic
19. Ilustrujte a vysvětlete princip přidělování paměti souborů na disku na bázi mapy souboru (str. 24-25)
-Potreba tabulka indexu – v ni je ulozena posloupnost bloku, ve kterych je prislusny soubor ulozen
- vhodne pro primy pristup k souborum
- Zadna externi fragmenace
- Index se při otevreni souboru nahrava do operacni pameti.
20. Vysvětlete princip vedení přehledu o volných alokačních blocích skupinovým adresováním volných alokačních bloků a uveďte základní vlastnosti této metody (str. 26).
- Princip pridelovani volneho mista na disku
- Jista analogie indexoveho pridelovani, ale pro volne bloky = snadnejsi hledani souvisleho volneho prostoru
21. Uveďte vlastnosti B stromu (str. 69…).
- m-arni vyvazeny strom
- Kombinace stromoveho a indexoveho vyhledavani
- Ukazatele na jednotlive zaznamy mohou byt jiz v uzlech = neredundance zaznamu
- Není umozneno sekvencni prochazeni zaznamu na listove urovni – nektere ukazatele mohou byt jiz v nekterych nelistovych uzlech
- Hloubka h = log m n
22. Kolik úrovní má binární strom o 13 uzlech? (str. 69).
- log 2 13 – cela horni část = 4
23. Vyjádřete obecný vztah mezi počtem úrovní binárního stromu a počtem uzlů (str. 69).
- cela horni část z log 2 n
24. Uveďte alespoň 3 příklady typických principů hašovacích funkcí (str. 54).
1) Hasovani na zaklade celociselneho deleni poctu zaznamu
h(k) = k mod M, kde M je počet kapes, do kterych se budou zaznamy ukladat
- Nejvice pouzivane
- Dobre rovnomerne rozdeleni
2) Změna ciselne sousavy na vyssi = dosazeni dobře rovnomerneho rozdeleni do kapes
3) Mid Square = funkce urcena pomoci druhé mocniny klice (popripade části klice)
- Vysledky jsou dobře nahodne
25. Charakterizujte cíl operace "otevření souboru", zmiňte přitom problematiku identifikace souboru a sdílení souboru (str. 19, 22).
- Cilem je zjistit, zda dany soubor existuje, zda ma prosec prava ho cist (zapisovat, pracovat)
pote ho nahrat do operacni pameti a nastavit ukazatel na prislusne místo v souboru
1) proces dava pozadavek OS
2) OS preda rizeni File Manageru
3) Kontrola existence, prav, vyhledani souboru na mediu
4) Nahrani potrebnych dat do operacni pameti
26. Jakou složitost má rešení dotazu nad sekvenčním souborem, nad uspořádaným sekvenčním souborem a nad uspořádaným sekvenčním souborem s blokovanými záznamy, má-li blokovací faktor hodnotu b (str. 40).
- Nad sekvencnim neusporadanym subrem = linearni O(N)
- Nad usporadanym souborem – pomoci metody puleni inervalu = O(log 2 N)
- S blokovacim zaznamem delky b O(log 2 N/b)