1. opravny termin:

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.