Staonův svět - Algoritmy a datové struktury - zkouška 27.6. Hric

Omluvte prosím menší zpoždění tohoto článku. Snad budou tyto informace ještě někomu k užitku.

Nejdřív jsme ráno přišli na písemnou část. Dává 3 otázky, každá se dělí ještě na 2 podotázky, které spolu většinou souvisí.
(otázky jsou volně interpretovány, není to přesný opis zadání)

1. a) Popište všechny případy mazání v AVL stromech.
b) Popište vkládání do B-stromů.

2. a) Dokažte nebo vyvraťte:
Pokud f(x) náleží o(h(x)) a g(x) náleží o(h(x)), potom f(x) + g(x) náleží o(h(x)).
b) Dokažte SUMA(i*n/(2^i))od 1 do log(n) (tady si to přesně nepamatuji) je O(n) pro n=2^k.

3. a) Navrhněte algoritmus metodou rozděl a panuj pro hledání mediánu ve dvou setříděných posloupnostech.
b) Najděte pro něj rekurzivní vzorec a spočítejte ho pomocí Master Theorem nebo substituční metodou (nebo tak nějak).

Bylo na to 1,5 hodiny. Docela to stačí.

Odpoledne na ústních každý dostane jednu otázku. Mě nechal napsat vše o otevřeném hashování.
Celkově je docela hodný, ačkoliv jsem měl menší výpadek u AVL stromů, dostal jsem celkově za jedna.

Michal

Matfyz | 29.6.2006 Čt 13:57 | <<< trvalý odkaz >>> | tisk | 0 komentářů

Komentáře k textu

Rss komentářů tohoto textu

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Autor stránek Staonův svět se jmenuje?
Odpověd: Staon Cornelius Latipus

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).