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í.

Nějaké informace, co se mohou hodit ke zkoušce, najete i na hlavní stránce předmětu.

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. Počáteční běhy se vytvářejí vylepšeným heapsortem, tzv. metodou dvojité haldy, 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í nebo část 2.7.4 ve skriptech).

Následně se běhy slévají obyčejným heapsortem (to ale není příliš podstatné), důležité je, že platí: délka konečné setříděné posloupnosti ≤ #cest^#průchodů

[F] Vnejsim tridenim jsme ziskali 625 behu. Kolikacestne slevani musite pouzit, abychom po dvou pruchodech daty dostali finalni setridenou posloupnost?
25cestné, protože 25² = 625.
[F] Kolikacestné třídění potřebujeme k setřídění 7897 údajů na 3 běhy (terminologická pozn. spíše průchody než běhy)?
20cestné, protože 20³ = 8000 ≥ 7897 > 6859 = 19³ (20cestné stačí, 19cestné by nestačilo). Pokud by skutečně byly míněny běhy a ne průchody, nelze na otázku bez dalších údajů jednoznačně odpovědět.
[P] Mějme posloupnost čísel 36, 70, 50, 61, 90, 55, 72, 31, 19, 24, 35, 8, 15, 28, 5.
(a) Kolik vzestupných běhů vytvoříme pomocí dvojité haldy o velikosti 7 prvků z výše uvedené posloupnosti?
(b) Kolik sestupných běhů bychom z uvedené posloupnosti za obdobných podmínek vytvořili?
(a) V prvním případě jsou všechny prvky, které se napoprve do haldy nevejdou (31, 19, …) menší než první prvek, který jsme z haldy vyplivli na výstup jako první (36, minimum prvních 7 prvků). Nemůžeme je tedy už do běhu (resp. haldy) zařadit. Druhý běh tedy vznikne tedy z prvků (31, 19, … 28), prvek 5 je opět menší než první prvek, který z haldy vyhodíme (8), takže ani ten «nevmáčkneme» do druhého běhu, vyjde na něj samostatný, třetí běh.
(b) V druhém případě, díky tomu, že posloupnost už je «téměř» sestupně uspořádaná, se nám podaří vše setřídit v jednom běhu, tj. každý osmý a další prvek můžeme vložit do haldy na uvolněné místo, opravit invarianty, vyhodit maximum, a tak dále.

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:

[F] Mejme disk s 4200 RPM. Vypocitejte jeho rotacni zpozdeni (uvedte postup).
Rotační zpoždění alias latence: r = (průměrně) 1/2 trvání otáčky = 1 / 2f = 1 / (2*4200 min^-1) = 1 / (2*4200/60 s^-1) = 1/140 s (přibližně 7 ms)
[F] Co všechno a jak lze zjistit z otáček disku?
Viz výše (r). (Nic jiného mě nenapadá)
[F] Co je tercialni pamet?
[F] Co je to jukebox?
[F] Mame radic, ktery umi RAID 0, RAID 1. RAID 5 a nezavisle disky. Napiste ve ktere situaci je vhodne vyuzit kterou metodu a proc.
POZOR: Spousta lidi si nevsimla ze jednou z moznosti jsou i nezavisle zapojene disky a tudiz popisovali jen RAID X.
[F] Mam 2 disky. Poradte mi, jak je mam v konkretnich situacich zapojit.

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?
Aspoň dva na případné slévání se sousední stránkou. Dva vyžaduje i případné smrštění adresáře. Operace by se udělaly po sobě, takže celkem dva.

(b) Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?
Čtu 1 stránku adresáře (1). Načtu stránku s daty (2), smažu z ní záznam, načtu sousední stránku s daty (nemusím znova číst adresář, je v téže části) (3), sliju obě stránky, zapíšu slitou stránku (4), načtu zbylou stránku adresáře (5 / kdybych byl hloupý, načtu znova obě: 6), smrštím adresář, zapíšu nový adresář (6/7 viz minulá operace).
[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]

Pro zajímavost: V pseudokódu na slajdech se v Insertu používají 3 buffery (buﬀer,pg,pg1), do jednoho se načte a do dvou zbylých se případně štěpí (nechme stranou, že čtvrtý buffer se zbytečně alokuje v Access). To by šlo snadno redukovat na dva, štěpilo by se pak částečně in-place. Je pravda, že to jde i na jeden za cenu jednoho čtení z disku navíc.

(b) jaka je nejhorsi I/O pri INSERTU [3]

Tj. čtení a dva zápisy při rozštěpení, na to ale potřebujeme aspoň ty dva buffery. S jedním bufferem, čtení, zápis jedné rozštěpené stránky, čtení, zápis druhé rozštěpené stránky — 4.

Evidentně se předpokládá, že adresář se vejde do stránky tj. má max. 256 položek. V otázce by asi mělo být, koli bitů se bere v úvahu.

(d) pocet hasovanych bitu z adresy je 8, kolik muze byt maximalne stranek po 1KB, ktere jsme schopni naadresovat. [2^8]

Velikost stránky není podstatná, využije se až v další otázce.

(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)
//Jestli "(1)" má být správná odpověď, tak je to IMHO blbost. 46 mod 11 = 2, takže v úvahu připadá pozice 2 nebo 3. Otázka je, co znamená to b=3. Podle mě by to mělo znamenat, že na každou pozici se vejdou tři záznamy, tj. předpokládám, že pozice jsou po blocích. Pak by se umisťovalo na pozici 2 ke klíči K3.
(b) Popiste co je potreba udelat pri Delete(12) (2)
12%11=1, tj. mažu 12 z pozice 1.

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)

Další nesetříděné

Viz soubory.