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 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}.

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".

3. 6. dopoledne

1. Popište a analyzujte Floydův-Warshallův algoritmus na výpočet matice vzdáleností.
2. Definujte (a,b)-strom a popište operaci Insert.
3. Na vstupu je posloupnost znaků. Spočítejte, kolikrát se v něm vyskytuje vybraná podposloupnost KOCKA.
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.

3. 6. odpoledne

1. Popište a analyzujte algoritmus pro hledání mostů v neorientovaných grafech.
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. 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.

5. 6. odpoledne

1. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
2. Definujte minimální kostru grafu a ukažte jeden efektivní algoritmus na její nalezení.
3. Je dána posloupnost čísel x₁, …, x_n a číslo s. Spočítejte, kolik existuje dvojic indexů (i,j) takových, že x_i + x_j = s.
4. Je dán orientovaný graf s určeným počátečním a cílovým vrcholem, v některých vrcholech se prodává zmrzlina. Najděte sled z počátečního do koncového vrcholu, který navštíví co nejvíce různých vrcholů se zmrzlinou.

11. 6. dopoledne

1. Popište a analyzujte algoritmus Quickselect, rozeberte vliv volby pivota na složitost.
2. Definujte AVL strom a popište operaci Insert.
3. Lagrangeova věta říka, že každé přirozené číslo x jde rozložit na součet čtyř čtverců (druhých mocnin celých čísel). Navrhněte algoritmus, který pro všechna x=1,…,n tyto rozklady najde.
4. Je dán neorientovaný graf s hranami ohodnocenými čísly z množiny {1,…,5}. Najděte jeho minimální kostru.

11. 6. odpoledne

1. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.
2. Definujte c-univerzální systém hešovacích funkcí. Ukažte, jak ho použít. Předveďte konstrukci nějakého takového systému.
3. 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í.
4. 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ý.

12. 6. odpoledne

1. Popište prohlédávání do hloubky a klasifikaci hran.
2. Popište a analyzujte algoritmus pro hledání k-tého nejmenšího prvku v lineárním čase.
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. Najděte k-tou permutaci na množině {1,…,n} v lexikografickém pořadí.

19. 6. odpoledne

1. Popište a analyzujte datovou strukturu Union-Find.
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. 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ě?

25. 6. dopoledne

1. Popište a analyzujte algoritmus pro násobení čísel metodou Rozděl a panuj.
2. Definujte (a,b)-strom a popište operaci Insert.
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 celých čísel. Najděte její nejdelší vybranou posloupnost, která je bitonická, tedy nejprve roste, pak klesá.

25. 6. odpoledne

1. Popište a analyzujte algoritmus pro hledání mostů v neorientovaných grafech.
2. Popište a analyzujte algoritmus pro výpočet editační vzdálenosti řetězců.
3. 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 z bludiště dostat ven.
4. Je dána posloupnost N navzájem různých celých čísel. Najděte její 1. až K-tý nejmenší prvek.

26. 6. odpoledne

1. Popište a analyzujte Quicksort.
2. Popište a analyzujte Floydův-Warshallův algoritmus.
3. Je dán DAG a počáteční a cílový vrchol. Spočítejte, kolik mezi nimi vede cest liché délky.
4. Sestrojte datovou strukturu pro množinu, která bude navíc umět operaci Count(x,y), jež efektivně spočte, kolik hodnot z množiny leží v intervalu [x,y].

Minulé roky

• 2023
• 2021
• 2015
• 2013
• 2011
• 2009