Zkouškové otázky z Algoritmů a datových struktur I

23. 5. (předtermín)

  1. Formulujte Mergesort a analyzujte jeho složitost.
  2. Definujte komponenty silné souvislosti orientovaného grafu. Popište a analyzujte algoritmus na jejich nalezení.
  3. Č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).
  4. 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

  1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
  2. Formulujte a dokažte Kuchařkovou větu o rekurencích.
  3. Je dáno čtverečkové bludiště. Najděte cestu ze startu do cíle, která projde co nejméně zdmi.
  4. 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

  1. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
  2. Definujte AVL strom a popište operaci Insert.
  3. Je dán neorientovaný graf. Zjistěte, zda je bipartitní.
  4. 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

  1. Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
  2. Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
  3. Je dán strom, jehož hranám jsou přiřazeny celočíselné délky. Najděte nejdelší cestu.
  4. 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

  1. Definujte (a,b)-strom a dokažte lemma o jeho hloubce.
  2. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
  3. 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.
  4. 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".

Minulé roky

Stránku spravuje Martin Mareš