Toto je stará verze stránky OrganizaceAZpracováníDat/ZkouškovéPříklady z 2009-01-12 11:58:02..

Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256 Deprecated: Function split() is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/classes/WackoFormatter.php on line 256

OZD – zkouškové příklady

aneb Kategorizovaný sborník

Zdroje: soubory zkouskove_pisemky.txt ([Z]), 060123-ZK-A.pdf, 060130-ZK-C.pdf ([P]), co se povalují na netu a fórum ([F]).

Snažím se setřídit dostupné příklady. Sám to asi nezvládnu, ale můžete se taky zapojit. Současný stav: Jsou setříděné příklady na Hashování ze zdrojů [P] a [Z].

Hashování

[P]Mějme v lineárním (Litwinově) hašování jedinou stránku s hašovanými hodnotami prvků 0101100, 1011000, 1010000, 0100000, 11101100. Stránka se musí rozštěpit. Rozdělte proto uvedené hodnoty do stránek 0 a 1.

0 1
[P] Mějme v lineárním (Litwinově) hašování pět stránek (0–4) s hašovanými hodnotami prvků 1100110, 0101011, 1110111, 0010010, 1001100, 0111000, 0101010, 1010101, 0011001, 1010110.
(a) Musí dojít k dílčí expanzi. Rozdělte proto uvedené hodnoty do stránek 0–5.

0 1 2 3 4 5

(b) Kterou stránku jsme rozštěpili?
[P] Rušíme záznam v souboru organizovaném v rozšířitelném (Faginově) hašování s adresářem ve dvou stránkách na disku.
(a) Kolik bufferů (1 buffer = 1 stránka) je třeba alokovat ve vnitřní paměti?
(b) Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?
[P] Přidejte prvek 250 do tabulky hašované Faginovou metodou (rozšířitelné hašování a pomocným adresářem – h = K mod 128):
[P] Nechť při perfektním hašování Cromacka nastane níže uvedená situace:

	p	i	r
0	3	0	1
1	0	0	0
2	0	0	2
3	0	0	0
4	4	0	1

0	12
1	7
2
3	5
4	9
5
6
4

(a) Vložte prvek 2.
(b) Vložte poté prvek 19.

[Z] hashovani, k mod n, zadano jak vypada tabulka. otazka do jake stranky spadne zadany klic a kolik stranek se musi precist, hint: je tam zadano, kolik zaznamu se vejde do jedne stranky...

[Z] faginovo hashovani nebo-li externi. cena delete kdyz je adresar v pameti a cena v nejhorsim pripade kdyz je adresar na 2 strankach na disku

[Z] Cormackovo hashovani, napsat jak vypada tvar hashovaci funkce Hi(K,r) pro r=4, a najit takove i, aby Hi(K,4) byla perfektni pro hodnoty klicu 501, 503, 510, 512.

[Z] Mame Faginovno hasovani, kde adresar je rezidentne v pameti

(a) kolik je treba alokovat bufferu na INSERT [2 – slo by i s jednim, ale je to zbytecna prace navic]
(b) jaka je nejhorsi I/O pri INSERTU [3]
(c) adresar je na disku, jak se zmeni pocet I/O, kdyz ukazatel ma 4B, velikost stranky 1KB [6]
(d) pocet hasovanych bitu z adresy je 8, kolik muze byt maximalne stranek po 1KB, ktere jsme schopni naadresovat. [2^8]
(e) jaky nejvetsi soubor jste schopni v tomto pripade ulozit? [256 KB]

[Z] Mame Litwinovo hasovani, prave vznikla stranka s poradovym cislem jedna.

(a) kolikata expanze probiha? [prvni]
(b) rozdelte prvky mezi stranky [jen bylo treba vedet podle ktery bitu se ma delit, ale rikal, ze je to stejne jedno, jestli 1. nebo posl.]

[Z] Dotazy na castecnou shodu v hasovani. Primarni soubor se tremi atributy (N, RN, R), kterym odpovida postupne 4, 9 a 3 bity v klici. Adresa stranek je dlouha 2B. Jaka je cena dotazu na castecnou shodu s atributy N a R? [2]

[Z] Hashujeme pomoci fce k mod 11, b=3. Kolize se resi strategii “Umisti na nejblizsi volne misto”.

(a) Kam bude umisten klic 46 (1)
(b) Popiste co je potreba udelat pri Delete(12) (2)

0	K1
1	12
2	K3
3
4
5
6
7
8	K4
9	K5
10	K6

[Z] Litwinova metoda stepeni stranek. Pridali jsme 4. stranku (ma cislo 3).

(a) Kolikata skoncila expanze? [1]
(b) Necht ve strance 1 jsou zaznamy 1001111, 1111011, 1010101, 1000001, 1110111. Provedte dalsi expanzi, tj. rozdelte do stranek. [2]

[Z] rozsiritelne hasovani. adresar podle hornich 4 bitu.

(a) kolik bufferu v RAM na INSERT (1)
(b) kolik I/O operaci (1)
(c) velikost adresare pro adresy 4B (1)
(d) velikost stranky je 2K, adresar na disku. jak se zmeni odpoved b) (1)
(e) max. velikost souboru s timto adresarem. (1)

OZD – zkouškové příklady

aneb Kategorizovaný sborník

Hashování

Nesetříděné