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

22. 5. (předtermín)

1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
2. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
3. Je dán strom, jehož hranám jsou přiřazeny celočíselné délky. Najděte nejdelší cestu.
4. Inverze v číselné posloupnosti x₁, …, x_n je taková dvojice indexů (i,j), pro kterou platí i<j a současně x_i > x_j. 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}.

25. 5. dopoledne

1. Popište prohlédávání do hloubky a klasifikaci hran.
2. Definujte (a,b)-strom a popište operaci Insert.
3. Je dána množina celých čísel a číslo S. Najděte trojici (ne nutně různých) prvků množiny, jejichž součet je roven S.
4. Je dán DAG a počáteční a cílový vrchol. Spočítejte, kolik mezi nimi vede cest liché délky.

25. 5. odpoledne

1. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
2. Formulujte a dokažte Kuchařkovou větu o rekurencích.
3. Je dáno číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšte medián z posledních K čísel.
4. Navrhněte algoritmus na obarvení rovinného grafu 6 barvami.

30. 5. dopoledne

1. Formulujte Mergesort a analyzujte jeho složitost.
2. Definujte AVL strom a popište operaci Insert.
3. Mějme orientovaný graf, jehož hrany jsou ohodnocené pravděpodobnostmi. Najděte nejpravděpodobnější cestu mezi dvěma vrcholy, tj. takovou, na níž je součin pravděpodobností hran největší možný.
4. Spočítejte, kolik existuje dláždění obdélníka 3×N kostkami 1×2 (lze je otáčet).

30. 5. odpoledne

1. Definujte písmenkový strom (trii) a popište operace na něm.
2. Popište a analyzujte algoritmus pro hledání k-tého nejmenšího prvku.
3. Je dáno čtverečkové bludiště. Najděte cestu ze startu do cíle, která projde co nejméně zdmi.
4. Najděte k-tou permutaci na množině {1,…,n} v lexikografickém pořadí.

1. 6. dopoledne

1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
2. Popište a analyzujte algoritmus pro hledání nejdelší rostoucí podposloupnosti.
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. Na vstupu je text rozdělený na slova. Vypište seznam unikátních slov (setříděný lexikograficky) spolu s počty jejich výskytů.

1. 6. odpoledne

1. Definujte AVL strom a dokažte větu o jeho hloubce.
2. Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
3. Hledáme nejkratší cestu čtverečkovým bludištěm, která se vyhne strážím. Každá stráž chodí po cyklu délky nejvýše 10.
4. Na vstupu je posloupnost znaků. Spočítejte, kolikrát se v něm vyskytuje vybraná podposloupnost KOCKA.

5. 6. dopoledne

1. Popište a analyzujte algoritmus Mergesort.
2. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
3. Je dána posloupnost N navzájem různých celých čísel. Najděte její 1. až K-tý nejmenší prvek.
4. Je dán orientovaný graf s určeným počátečním vrcholem, v některých vrcholech se prodává zmrzlina. Najděte sled vycházející z počátečního vrcholu, který navštíví co nejvíce různých vrcholů se zmrzlinou.

5. 6. odpoledne

1. Formulujte a dokažte Kuchařkovou větu o rekurencích.
2. Popište a analyzujte algoritmus pro hledání mostů v neorientovaných grafech.
3. Je dána posloupnost přirozených čísel. Spočítejte, kolik má vybraných podposloupností, jejichž součet je dělitelný 7.
4. Mějme bludiště ve tvaru čtvercové sítě, jejíž políčka obsahují místnosti, zdi, klíče K₁ až K_k a odpovídající zamčené dveře D₁ až D_k. Dveřmi D_i je možno projít, pokud jste předtím alespoň jednou navštívili políčko s klíčem K_i. Vymyslete algoritmus, který zjistí, zda se jde dostat ven z bludiště.

9. 6. dopoledne

1. Hešování a systémy hešovacích funkcí.
2. Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
3. Nalezněte v zadaném stromu největší párování: to je podmnožina hran taková, že žádné dvě hrany nemají společný vrchol.
4. Vymyslete co nejefektivnější algoritmus pro K-cestné slévání: slití K setříděných posloupností o celkové délce N. Jak se změní časová složitost Mergesortu, když budeme dělit na K částí a slévat K-cestně?

9. 6. odpoledne

1. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
2. Popište a analyzujte Bellmanův-Fordův algoritmus pro hledání nejkratší cesty.
3. Je dán slovník. Sestrojte co nejdelší slovní žebřík. To je posloupnost slov ze slovníku taková, že (i+1)-ní slovo získáme z i-tého smazáním jednoho písmene. Například pro anglický slovník AGID-4 vychází žebřík glassiness, glassines, glassine, glassie, lassie, lassi, lass, ass, as, a.
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.

13. 6.

1. Popište a analyzujte algoritmus pro hledání k-tého nejmenšího prvku.
2. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
3. 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.
4. Je dán neorientovaný graf. Jak množinu jeho hran rozložit na hranově disjunktní cesty délky 2? (Tedy tak, aby každá hrana ležela v právě jedné cestě.) Pokud si nevíte rady s obecným grafem, zkuste to nejdřív pro strom.

15. 6. dopoledne

1. Popište reprezentaci množiny řetězců písmenkovým stromem (trií) a operace na ní.
2. Definujte komponenty silné souvislosti orientovaného grafu. Popište a analyzujte algoritmus na jejich nalezení.
3. Je dán orientovaný graf, jehož hrany jsou ohodnoceny nezápornými délkami, a počáteční a cílový vrchol. Chceme najít takovou nejkratší cestu, která má co nejméně hran.
4. Sestrojte vyhledávací strom, který bude navíc umět operaci Count(x,y), která v logaritmickém čase spočte, kolik hodnot ve stromu leží v intervalu [x,y].

15. 6. odpoledne

1. Výpočetní model RAM: defince, zavedení složitosti.
2. Definujte AVL strom a popište operaci Insert.
3. Je dána posloupnost navzájem různých celých čísel. Spočítejte, kolik v ní je rostoucích podposloupností.
4. Uvažujme posloupnost, která je setříděná až na K prvků, které jsou zatříděny chybně (knížky v knihovně hojně navštěvované čtenáři). Navrhněte co nejefektivnější algoritmus (vzhledem k počtu prvků a K), který posloupnost dotřídí.

21. 6.

1. Popište prohlédávání do hloubky a klasifikaci hran.
2. Definujte (a,b)-strom a popište operaci Insert nebo Delete.
3. Je dán DAG s ohodnocenými hranami, počáteční a koncový vrchol. Najděte všechny hrany, které leží na aspoň jedne nejdelší cestě mezi danými vrcholy.
4. Na vstupu je posloupnost znaků. Spočítejte, kolikrát se v něm vyskytuje vybraná podposloupnost KOCKA.

22. 6. dopoledne

1. Formulujte a dokažte Kuchařkovou větu o rekurencích.
2. Vyslovte a analyzujte Bellmanův-Fordův algoritmus na hledání nejkratší cesty.
3. 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.
4. Je dán strom, jehož vrcholy jsou ohodnocené celočíselnými cenami. Najděte co nejlevnější podmnožinu vrcholů, která protíná každou hranu.

22. 6. odpoledne

1. Popište a analyzujte algoritmus pro hledání k-tého nejmenšího prvku.
2. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
3. Labyrint má tvar čtvercové sítě, některá políčka jsou zdi. Archeolog se chce dostat z políčka A na políčko B. Projít na volné políčko mu trvá 1 minutu, prokopat se na políčko se zdí 20 minut. Najděte nejrychlejší cestu.
4. Je dáno liché číslo K. Na vstupu přichází celá čísla, po příchodu dalšího čísla vždy vypíšte medián z posledních K čísel.

29. 6. dopoledne

1. Popište a analyzujte Dijkstrův algoritmus na hledání nejkratší cesty.
2. Formulujte Mergesort a analyzujte jeho složitost.
3. Máme N obdélníků, které je možno otáčet o násobky 90 stupňů. Vyrobte z nich co nejdelší posloupnost, ve které se každý obdélník vejde do následujícího.
4. Je dán orientovaný graf s určeným počátečním vrcholem, v některých vrcholech se prodává zmrzlina. Najděte sled vycházející z počátečního vrcholu, který navštíví co nejvíce různých vrcholů se zmrzlinou.

29. 6. odpoledne

1. Definujte AVL strom a popište operaci Insert.
2. Popište prohledávání do šířky a ukažte, jak se pomocí něj detekují cykly v orientovaných grafech.
3. Kdesi v bludišti se nachází robot. Vysíláme posloupnost příkazů (každý příkaz je nějaký pohyb o jedno políčko na sever/jih/východ/západ) pořád dokola, než robot vyleze z bludiště (pokud robot nemůže příkaz provést, protože by narazil do zdi, ignoruje ho). Zjistěte, zda pro danou mapu bludiště a danou posloupnost příkazů platí, že ať robot na počátku stojí kdekoliv, vždy je vysvobozen.
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.

Minulé roky

• 2021
• 2015
• 2013
• 2011
• 2009