zkouška 10-6-2009 HRIC

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
ian
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 14. 2. 2009 15:21
Typ studia: Informatika Mgr.

zkouška 10-6-2009 HRIC

Příspěvek od ian »

Dnes jsme tam byli jen čtyři, písemná část klasicky 3 x 2 otázky za 15 bodů celkem.

1 a) delete v AVL stromech
b) dokázát, že výška RB-stromu je O(log n)
2 a) dokázát nebo vyvrátit, že v souvislém grafu je množina všech lehkých hran pro všechny řezy minimální kostra
b) složitost Jarníkova (Primova) algoritmu v závislosti na volbě datových struktur
3 a) definovat topologické uspořádání
b) popsat algoritmus na hledání nejkratší cesty v acyklickém grafu a dokázat jeho správnost

na ústím jsem dostal dolní odhad složitosti třídicích algoritmů založených na porovnávání prvků
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“