Test Algo Flashcards
Algoritmus Insertion sort je:
v nejlepším případě třídí se složitostí O(n) v nejhorším případě třídí se složitostí O(n^2) stabilní přirozený
Algoritmus Selection sort je:
v nejlepším případě třídí se složitostí O(log(n)) in place stabilní
Kolik nejvíce uzlů může obsahovat binární vyhledávací stromu o hloubce 3 (hloubka stromu je měřena počtem hran; resp. největší délka cesty z kořene do listů)
15
8-bitová Floating point reprezentace čísel na počítači může reprezentovat:
některá racionální čísla všechna celá čísla mezi intervalem <0-255>
Pro binární vyhledávací strom (reprezentující množinu) platí:
pro hodnoty uzlů stromu vždy platí, že hodnota levého syna je menší než hodnota uzlu
pro hodnoty uzlů stromu vždy platí, že hodnota pravého syna je větší než hodnota uzlu
Budu-li vkládat čísla do hashovací tabulky pak:
mohou nastat kolize
32bitová Floating point reprezentace čísel na počítači umí reprezentovat
některá racionální čísla
Jaká je největší hloubka nejvíce degenerovaného binárního vyhledávacího stromu s 5 vrcholy? (hloubka stromu je měřena počtem hran; resp. největší délkou cesty z kořene do listů)
4
Nejlepší třídící algoritmus založení na třídění porovnáváním prvků třídí v nejlepší složitosti v nejhorším případě:
O(nlog)
Vlastností degenerovaného binárního vyhledávací stromu je
vyhledání prvku je ve složitosti O(výška stromu) odebrání prvku ze stromu je ve složitosti O(výška stromu)
16-bitová Floating point reprezentace čísel na počítači může reprezentovat:
některá racionální čísla
Odebráním jednoho vrcholu z binárního vyhledávacího stromu se může
výška stromu zůstat stejná výška stromu snížit o 1
Mezi algoritmy založené na principu „rozděl a panuj“ patří:
merge sort quicksort
Budu-li mazat ve stromě t kořen – operace: delete(15), které vrcholy ho mohou nahradit?
20 12
Odebírám-li kořen z (neprázdné) haldy o 4 hladinách vhodného kandidáta na nový kořen (k probublání) naleznu mezi vrcholy:
vždy v poslední vrstvě nejvic v pravo
Počet vrstev binární haldy obsahující 5 prvků je (kořen haldy je v 1. vrstvě):
3
Kolik nejvíce uzlů může obsahovat binární vyhledávací strom o hloubce 2 (hloubka stromu je měřena počtem hran; resp. největší délka cesty z kořene do listů)
7
Binární maximová halda o 3 hladinách může obsahovat uzlů:
5 4 7
Pro binární vyhledávací strom (reprezentující množinu) platí:
může degenerovat
hodnota ůzlu stromu, hodnota pravého syna je větší než hodnota levého syna
hodnota pravého syna je větší než hodnota uzlu
Mějme strom t
7,12,10,31,20,15
Pro binární maximovou haldu plati
kazdy uzel ma max 2 potomky
hodnota leveho syna je mensi nez uzel
Počet vrstev binární haldy obsahující 5 prvků je (kořen haldy je v 1. vrstvě):
3
Pro maximovou haldu plati
hodnota vsech potomku je mensi nez hodnota uzlu
hodnota uzlu praveho potomka je mensi nez hodnota uzlu
