Algoritmy a dátové štruktúry

Tu su nejaké zadania teoretickej časti skúšky z ADS.

1. opravny termin: (05.01.2006)

1. Definujte predpoklad uniformneho hasovania. Vymenujte tri strategie riesenia kolzii pri zatvorenom hasovani. Ktora z nich sa najviac z nich priblizuje predpokladu uniformneho hasovania? Preco?
2. B je velkost tabulky, N je pocet prvkov.
a. Najdite reprezentaciu pre otvorene hasovania, kde ocakavany cas neuspesneho vyhladavania je O(1+lg(N/B)).
b. Aky bude ocakavany cas uspesneho vyhladavania pri tejto strategii? Podrobne zdovodnite.
3. Aky moze byt maximalny rozdiel dlzok dvoch ciest od korena po list v cerveno ciernom strome? Zdovodnite.
4. Ako sa lisia minimalne a maximalne pocty prvkov, ktore mozu byt v 2-3 strome a v B strome stupna aspon t=2 vysky h? Zdovodnite.
5. Nakreslite postupnost AVL stromov, ktore vzniknu pridavanim prvkov 13, 15, 27, 7, 5, 8, 17, 13, 21, 14, 21 do prazdneho AVL stromu a naslednym odoberanim prvkov 8, 17, 14, 13, 5, 3, 15.
6. V Pascale definujte datovu strukturu pre stromovu reprezentaciu disjunktnych mnozin s operaciami UNION a FIND. Napiste nerekurzivnu funkciu FIND(x), ktora pracuje v case O(alfa(n)), kde alfa(n) je pseudoinverzna funkcia k Ackermannovej funkcii.
7. Nakreslite strukturu multilist zachytavajucu nasledovne vztahy: bicykle maju na sklade na Racianskej, Antolskej a Vazovovej; korcule maju na Racianskej a Dunajskej; sportovu obuv len na Dunajskej; sportove batohy drzia na Antolskej a Dunajskej a sportove odevy maju v sklade na Vazovovej.
8. Odhadnite pocet porovnani pri triedeni n-prvkov metodou kvadratickeho vyberu.
9. V pascale navrhnite datovu strukturu presity strom a implementujte proceduru VLOZ PRAVEHO, ktora vlozi vrchol q ako praveho syna vrcholu v. Ak vrchol v mal praveho syna, tento sa stane pravym synom vrchola q.
10. Preco nam treba dolne a horne odhady poctu porovnani optimalneho algoritmu vnutorneho triedenia a ako ich dosahujeme.

13.12.2005
1. Odvodte tesny horny odhad na uspesne vyhladavanie v hasovacej tabulke pre otvorene hasovania, ak prvky vkladame do zoznamov na zaciatok.
2. Je dana hasovacia tabulka velkosti B=13 pre zatvorene hasovanie. Vkladali sa do nej prvky v poradi 24, 7, 34, 20, 13, 8, 33, 21.
a. Zistite, aka hasovacia funkcia a aka strategia riesenia kolizii bola pouzita. Urcte prislusnu konstantu (konstanty).
b. Ako by sa tabulka zmenila, keby sme prvky vkladali v opacnom poradi?
tabulka: 13, 21, , , , , 33, 7, 34, 20, 8, 24, .
3. Ako vyzera najhorsi pripad AVL stromu s 22 vrcholmi? Nakreslite.
4. Nakreslite postupnost B-stromov s minimalnym stupnom 2, ktore vznikli postupnym vkladanim prvkov 200, 300, 100, 500, 50, 250, 450, 600, 150, 400, 270, 130, 210, 230, 70 do povodneho prazdneho stromu s naslednym vymazanim 150, 200, 300, 450.
5. Napiste proceduru, pomocou ktorej prerobite obycajny binarny strom na presity. Ich reprezentaciu si zvolte sami.
6. Aka je maximalna vyska cerveno-cierneho stromu, v ktorom je n prvkov? Dokazte.
7. Uvazujme stromovu reprezentaciu disjunktnych mnozin prvkov s operaciami UNION a FIND. Aka je casova zlozitost operacie FIND bez kompresie cesty, ak pri vykonavani operacie UNION vkladame mensiu do vacsej? Dokazte.
8. Vysvetlite, ako funguje rozkladove hasovanie a yvedte priklad jeho vyuzitia.
9. V Pascale napiste proceduru na utriedenie n-prvkoveho pola celych cisel algoritmom ShakerSort. Urcte zlozitost tohto triediaceho algoritmu.
10. Zadefinujte prislusne pojmy a vysvetlite pojmy dolneho a horneho odhadu na pocet porovnani optimalneho triediaceho algoritmu.

ADS pisomka 12.12.2006

1. Dany je binarny strom.Predpokladajme, ze mame k dispozicii nasledujuce 2 funkcie:
a)postorder(x) - vracia cislo vrchola x v postorderovskom usporiadani vrcholov daneho stromu
b)desc(x) - vracia pocet vlastnych nasledovnikov vrchola x v danom strome
Sformulujte pomocou nich vztah,ktory musi platit, ak je vrchol x nasledovnikom vrchola y v danom strome.

2. Vysvetlite ako funguje rozkladove hasovanie a uvedte priklad jeho pouzitia

3. Uvazujme zatvorene hasovanie s linearnym riesenim kolizii. Matematicky zdovodnite, preco bloky obsadenych miest maju tendenciu narastat.

4. Aka je maximalna vyska cerveno-cierneho stromu, ktory obsahuje n prvkov? Dokazte.

5. Nakreslite postupnost 2-3-stromov,ktore vzniknu vkladanim prvkov 5,10,21,33,27,12,19,15,37,17,3,18,4 do povodne prazdneho stromu a naslednym vymazanim prvkov 21,19,18.

6. Dany je B-strom minimalneho stupna t, ktory ma vysku h. Kolko prvkov moze obsahovat?
Odvodte obe hranice.

7. V Pascale zadefinujte datovu strukturu pre strommovu reprezentaciu mnozin s operaciami UNION a FIND a napiste proceduru UNION (A,B:nametype) (v Pascale), ktora zjednocuje prvky mnozin A a B tak, aby funkcia FIND(x) bez kompresie cesty bezala v case O(log2(n)), kde n je pocet prvkov ulozenych v strukture. (Funkciu FIND nemusite pisat, predpokladame, ze je taka, ako bola definovana na prednaske.)

8. Odvodte tesny horny odhad na ocakavany cas uspesneho vyhladavania v hasovacej tabulke pre otvorene hasovanie v pripade, ze prvky vkladame do zoznamov na zaciatok.

9. Vysvetlite, ako funguje algoritmus stromoveho triedenia a odvodte odhad jeho zlozitosti.

10. Nakreslite strukturu miltilist, ktora bude zachytavat nasledujuce vztahy medzi tovarmi a velkoskladmi. Bicykle maju vo velkosklade na Racianskej, na Antolskej a na Vazovovej.
Korcule maju na Racianskej a na Dunajskej. Sportovu obuv maju len na Dunajskej. Sportove batohy maju na Antolskej a Dunajskej a sportove odevy maju len na Vazovovej.

v TXT a DOC na stiahnutie tu:
http://www.subory.sk/download/211783/ADS.zip