BPC-ALD_Zpracované_otazky_ke_zkousce
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Předchůdce, Následník, Výška stromu. (++)
(Stejskal)
Výška stromu je vzdálenost nejvíce vzdáleného uzlu od kořene - počet hran mezi nimi.
2. Nakreslete vyvážený binární strom. Uveďte nutné podmínky definující
vyvážený strom. (+)
Ve všech vrstvách má maximální možný počet uzlů vyjma poslední vrstvy, která
může být zaplněna jen z části.
Maximální možný počet se myslí, že může mít maximálně dva následovníky,
protože je to binární strom.
3. Je dána např. posloupnost čísel: 7, 1, 2, 8, 2, 4, 5. Popište konkrétně jednotlivé kroky třídění pomocí haldy
(Heap Sort) a uveďte po každém kroku částečně setříděnou posloupnost zakreslenou jako stromovou
strukturu. (Uvažujme vzestupné třídění.) (+++)
Metoda začíná vytvořením tzv. výšky haldy, ta se spočítá jako h = log2(n). Sestavíme vyvážený binární strom o
dané výšce a vyplníme ho tříděnými prvky. Následně budeme odspodu procházet nelistové uzly a budeme
ověřovat, zda splňují podmínku haldy vzhledem ke svým následníkům (hodnota v následujícím uzlu je menší, než
v vyšším
ODKAZ KDE JSEM TO POCHOPIL
4. Jaké základní operace s prvky pole jsou využívány při třídění pomocí haldy (Heap Sort). Jaká je výsledná
míra složitosti v optimálním případě a jaká bude v nejhorším případě. (++)
Základná operace: srovnání a výměna
O(n*log(n)) - garantovaná vo všetkých prípadoch
Přednáška 12: Vnější třídění se stejným počtem vstupních a výstupních souborů, odvození
složitost algoritmu. (Ing. Tomáš Macho, Ph.D.)
1. Je dána např. posloupnost čísel: 7, 1, 2, 8, 2, 4, 5,9,0,11,15,3. Popište konkrétně jednotlivé kroky třídění
pomocí metody vnějšího třídění se stejným počtem vstup. a výstup. souborů. Ke třídění využijte 3 vstupní
a 3 výstupní soubory, které vhodně pojmenujte. Po zpracování každého vstupního běhu uveďte obsahy
výstupních souborů a označte jednotlivé běhy v těchto souborech. (Uvažujme vzestupné třídění.) (+++)