Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : Organizace A Zpracování Dat / Zkouškové Příklady
Přihlášení:  Heslo:  
Matfiz: OrganizaceAZpracováníDat/ZkouškovéPříklady ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |
Toto je stará verze stránky OrganizaceAZpracováníDat/ZkouškovéPříklady z 2009-01-14 00:14:47..

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 Pokus o kategorizovaný sborník


Zdroje: soubory file:zkouskove_pisemky.txt [Z], 060123-ZK-A.pdf, 060130-ZK-C.pdf [P], co se povalují na netu a fórum [F]. Tímto děkuji všem, kdo tyto zdroje publikovali (u souborů není úplně jasné, o koho jde)!


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], (nedávné) Obecné příklady z fóra a nějaké příklady na třídění.

Vnější třídění

Vnější třídění nebylo na přednášce(!), ale probíralo se na prvním cvičení. Občas se vyskytnou příklady i na něj. Třídí, resp. slévá, se vylepšeným heapsortem, který v případech «téměř setříděné» posloupnosti dokáže vytvořit i běhy delší (nikdy ne však kratší), než je velikost haldy (viz třeba tyto ne zcela jasné, ale pochopitelné, zápisky ze cvičení).


Musí platit: délka konečné setříděné posloupnosti#cest#běhů


Obecné

Obecné příklady jsem našel jen na fóru. Zdá se, že ve starších písemkách se nevyskytovaly. Celé fórum jsem neprocházel, ale to možná ani nemá smysl, tady jsou ty relativně nedávné z fóra:

Hashování


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
p i r
0301
1000
2002
3000
4401
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
012
17
2
35
49
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)
    0K1
    112
    2K3
    3
    4
    5
    6
    7
    8K4
    9K5
    10K6
  • [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)

  • Další nesetříděné

    Viz soubory.



     
    Na stránce nejsou žádné soubory. [Zobrazit soubory (formulář)]
    Na stránce nejsou žádné komentáře. [Zobrazit komentáře (formulář)]