Zkouškové otázky z Algoritmů a datových struktur I
23. 5. (předtermín)
- Formulujte Mergesort a analyzujte jeho složitost.
- Definujte komponenty silné souvislosti orientovaného grafu. Popište a analyzujte algoritmus na jejich nalezení.
- Čtverečkovou sítí s překážkami stěhujeme gauč tvaru "L" ze tří políček. Najděte cestu na co nejméně kroků (posun o 1 políčko, případně otočení na volném čtverci 2×2 pole).
- Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšeme minimum z posledních K čísel.
27. 5. dopoledne
- Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
- Formulujte a dokažte Kuchařkovou větu o rekurencích.
- Je dáno čtverečkové bludiště. Najděte cestu ze startu do cíle, která projde co nejméně zdmi.
- Je dána posloupnost celých čísel. Chceme najít nejdelší souvislý úsek, který obsahuje stejný počet kladných čísel jako záporných.
27. 5. odpoledne
- Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
- Definujte AVL strom a popište operaci Insert.
- Je dán neorientovaný graf. Zjistěte, zda je bipartitní.
- Inverze v číselné posloupnosti x1, …, xn je taková dvojice indexů (i,j), pro kterou platí i<j a současně xi > xj. Vymyslete algoritmus, který co nejefektivněji spočte, kolik je v posloupnosti inverzí. Můžete předpokládat, že posloupnost je permutací na množině {1,…n}.
29. 5. dopoledne
- Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
- Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
- Je dán strom, jehož hranám jsou přiřazeny celočíselné délky. Najděte nejdelší cestu.
- Je dána posloupnost přirozených čísel. Spočítejte, kolik má vybraných podposloupností, jejichž součet je dělitelný 7.
29. 5. odpoledne
- Definujte (a,b)-strom a dokažte lemma o jeho hloubce.
- Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
- Je dána posloupnost celých čísel a číslo S. Najděte trojici (ne nutně různých) prvků posloupnosti, jejichž součet je roven S.
- Je dána nějaká permutace π, která propojuje n levých konců kabelů s n pravými. Chceme tuto permutaci najít pomocí co nejmenšího počtu operací "nastav i-tý levý konec na hodnotu 0 nebo 1" a "zjisti hodnotu na j-tém pravém konci".