C2142: Příklady zkouškových otázek
1. Je algoritmus se složitostí O(n) vždy lepší než algoritmus se složitostí O(n log n)? Zdůvodněte.
2. Ukažte, že selection sort není stabilní řadicí algoritmus.
3. Jak a s jakou složitostí naleznete v minimové haldě druhý nejmenší prvek?
4. Popište na konkrétním příkladě výhody obousměrně zřetězeného seznamu oproti jednosměrnému. Jaké jsou
nevýhody?
5. Nakreslete jeden příklad rotace v AVL stromě. K čemu se rotací využívá?
6. Ukažte, že rozhodovací varianta problému obchodního cestujícího je v třídě NP.
7. Popiště algoritmus, který určí, zda jsou dvě slova přesmyčky (obsahují stejný počet stejných písmen). Tedy
např. LUSK a KLUS jsou přesmyčky, HLAD a SKLAD ne. Jaká je jeho složitost?
8. Jakým algoritmem byste vypsali binární strom po jednotlivých úrovních? Jaká je jeho složitost?
9. Co je to kolize při hashování a jakým způsobem se dá řešit?
10. Diskutujte rozdíly mezi polem a spojovým seznamem.
11. Popište merge sort a odvoďte jeho složitost.
12. Popište algoritmus, který určí výstupní stupeň vrcholu v orientovaném grafu reprezentovaném seznamem
následníků. Jaká je jeho složitost?
13. Ukažte, že rozhodovací varianta problému batohu je ve třídě NP. (Lze vložit do batohu nosnosti M předměty
s celkovou hodnotou alespoň V? Předměty mají hmotnosti m1, . . . , mk a hodnoty v1, . . . , vk.)
14. Ukažte příklad problému a jeho konkrétní instance, u které hladový algoritmus nedá (optimální) řešení.
15. Popište dva způsoby, jak lze reprezentovat zásobník. Jaká je v těchto případech složitost jednotlivých operací?
16. Uveďte rekurzivní a nerekurzivní podobu programu, který spočítá faktoriál přirozeného čísla. Je zde rozdíl
ve složitosti obou přístupů?
17. Popište algoritmus, který do orientovaného neohodnoceného grafu reprezentovaného maticí sousednosti
přidá opačné hrany, tj. pokud je v grafu hrana (u, v) a neexistuje hrana (v, u), tak ji algoritmus doplní.
18. Vysvětlete, v čem spočívá problém P vs. NP.
19. Co je to graf a jak jej lze reprezentovat? Ukažte na příkladu.
20. K čemu je algoritmus binárního vyhledávání? Jaká je jeho složitost? Jaké jsou vstupní podmínky pro tento
algoritmus.
21. Co znamená, pokud je řadicí algoritmus stabilní? Jak se dá tato vlastnost využít? Uveďte příklad stabilního
řadicího algoritmu.
22. Co je to prioritní fronta a jak byste ji implementovali? Jaká by byla složitost operací nad takovouto strukturou?
23. Zhodnoťe výhody a nevýhody rekurzivních algoritmů.
24. Popište obecný binární vyhledavací strom. Jaké standardní operace jsou na něm definovány? Čím je dána
složitost těchto operací? Uveďte konstrukci nejnepříznivějšího případu.
25. Diskutujte rozdíly ve složitosti přidávání prvku do dynamického pole v závislosti na zvolené pozici.
26. Popište datovou strukturu trie. Jak se liší od jiných struktur (např. binárního vyhledávacího stromu)?
27. Navhrněte datovou strukturu pro reprezentaci disjunktních podmnožin. Jaké operace byste nad touto strukturou
očekávali?
28. Vyjádřete počet kroků nutných pro vyřešení problému Hanoiských věží.
29. Jaký řadicí algoritmus byste použili, pokud by záměna dvou prvků byla velmi drahá operace. Zdůvodněte.
30. Srovnejte přístup rozděl a panuj s dynamickým programováním.