Test Algo

Question 1

Algoritmus Insertion sort je:

Answer 1

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ý

Question 2

Algoritmus Selection sort je:

Answer 2

v nejlepším případě třídí se složitostí O(log(n)) in place stabilní

Question 3

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ů)

Answer 3

15

Question 4

8-bitová Floating point reprezentace čísel na počítači může reprezentovat:

Answer 4

některá racionální čísla všechna celá čísla mezi intervalem <0-255>

Question 5

Pro binární vyhledávací strom (reprezentující množinu) platí:

Answer 5

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

Question 6

Budu-li vkládat čísla do hashovací tabulky pak:

Answer 6

mohou nastat kolize

Question 7

32bitová Floating point reprezentace čísel na počítači umí reprezentovat

Answer 7

některá racionální čísla

Question 8

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ů)

Answer 8

4

Question 9

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ě:

Answer 9

O(nlog)

Question 10

Vlastností degenerovaného binárního vyhledávací stromu je

Answer 10

vyhledání prvku je ve složitosti O(výška stromu) odebrání prvku ze stromu je ve složitosti O(výška stromu)

Question 11

16-bitová Floating point reprezentace čísel na počítači může reprezentovat:

Answer 11

některá racionální čísla

Question 12

Odebráním jednoho vrcholu z binárního vyhledávacího stromu se může

Answer 12

výška stromu zůstat stejná výška stromu snížit o 1

Question 13

Mezi algoritmy založené na principu „rozděl a panuj“ patří:

Answer 13

merge sort quicksort

Question 14

Budu-li mazat ve stromě t kořen – operace: delete(15), které vrcholy ho mohou nahradit?

Answer 14

20 12

Question 15

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:

Answer 15

vždy v poslední vrstvě nejvic v pravo

Question 16

Počet vrstev binární haldy obsahující 5 prvků je (kořen haldy je v 1. vrstvě):

Answer 16

3

Question 17

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ů)

Answer 17

7

Question 18

Binární maximová halda o 3 hladinách může obsahovat uzlů:

Answer 18

5 4 7

Question 19

Pro binární vyhledávací strom (reprezentující množinu) platí:

Answer 19

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

Question 20

Mějme strom t

Answer 20

7,12,10,31,20,15

Question 21

Pro binární maximovou haldu plati

Answer 21

kazdy uzel ma max 2 potomky

hodnota leveho syna je mensi nez uzel

Question 22

Počet vrstev binární haldy obsahující 5 prvků je (kořen haldy je v 1. vrstvě):

Answer 22

3

Question 23

Pro maximovou haldu plati

Answer 23

hodnota vsech potomku je mensi nez hodnota uzlu

hodnota uzlu praveho potomka je mensi nez hodnota uzlu