Kód: Vybrat vše
1. Přidejte ke každému vrcholu v n-árním stromě dvě přirozená čísla. První je číslo pořadí vrcholu při průchodu preorder, druhé při průchodu postorder (zleva).Kód: Vybrat vše
2. Hladovým algoritmem sestrojte v daném grafu nezávislou množinu vrcholů, která nejde zvětšit přidáním vrcholu.Kód: Vybrat vše
3. V binárním stromě některé prvky porušují podmínky uspořádání na binární vyhledávací strom. Vydejte seznam vrcholů, které uspořádání porušují a počet úrovní (od vrcholu ke kořeni), na kterých ho porušují.Kód: Vybrat vše
4. Je dán orientovaný graf a rozklad jeho vrcholů do tříd ekvivalence. Sestrojte nový graf, ve kterém spojíte všechny vrcholy z jedné třídy do jednoho vrcholu-reprezentanta.
Kód: Vybrat vše
Alokace registrů:
Hradlová síť je množina hradel, kde každé hradlo má jediný výstup, svoje jedinečné jméno a seznam vstupů (s daným pořadím). Vstupy jsou buď jména jiných hradel nebo jméno vstupních bodů sítě. Síť je acyklická, tzn. žádné hradlo není závislé na svém výstupu. Vstup programu je hradlová síť. Úloha je
a) uspořádat hradla tak, aby každé hradlo bylo až za hradly, které počítají jeho vstupy
b) Přiřadit vstupním bodům sítě a výstupům hradel "registry CPU". Registr můžete použít pro výsledek dalšího hradla, pokud hodnota z něho již nebude potřeba pro vstup žádného hradla.
Výstupní registr je vždy různý od všech vstupních registrů (pro každé hradlo). Počet registrů není omezený, ale snažte se heuristicky použít jich co nejmenší počet. Tj. vyhněte se triviálnímu řešení kdy výsledku každého hradla je přiřazený jiný registr.Kód: Vybrat vše
2