1. Każdy węzeł drzewa BST posiada pola: * key, left, parent, child * key, left, right * key, left, right, parent * key, left, right, child 2. Przeszukiwanie drzewa BST jest możliwe: * tylko rekurencyjnie * tylko iteracyjnie * rekurencyjnie i iteracyjnie - z różną złożonością obliczeniową * rekurencyjnie i iteracyjnie - z taką samą złożonością obliczeniową 3. W jaki sposób należy usuwać węzeł z drzewa BST, jeżeli ma on 2 potomków? * należy zastąpić węzeł jego następnikiem * należy przenieść dzieci do rodzica * należy ustawić wskaźnik rodzica na null * należy przenieść dzieci do przypadkowego węzła 4. Zasadniczo klucze drzewa BST: * mogą być dowolne, z tym że korzeń musi mieć klucz numer 1 * mogą być dowolne, z tym że potomek nie może mieć takiego samego klucza jak jego rodzic * muszą być unikatowe * mogą być dowolne, z tym że korzeń musi mieć klucz o najwyższej wartości 5. Pesymistyczny koszt operacji dla zrównoważonego drzewa BST wynosi: * n * log_2 n * n^2 * log_n 2 6. Pesymistyczny koszt operacji dla drzewa BST zdegenerowanego do listy wynosi: * n * log_2 n * n^2 * log_n 2 7. Aby utworzyć drzewo BST posługujemy się drzewem: * zstępującym 2-3-4 * binarnym * B-drzewem * wyważonym drzewem czerwono-czarnym 8. Następnik x w drzewie BST to: * prawy potomek x * lewy potomek x * najmniejszy element y wśród elementów większych od x * największy element y wśród elementów mniejszych od x 9. Następnikiem x w drzewie BST jest: * null jeśli x jest najmniejszym z węzłów * maksimum w prawym poddrzewie t jeśli ono istnieje * największy z przodków x, dla których lewy potomek jest przodkiem x * null jeśli x jest największym z węzłów 10. Wstawiając element do drzewa BST: * można to zrobić w dowolnym miejscu * nie ma znaczenia czy dowiążemy element jako potomek lewy czy prawy * nie jest istotna wartość klucza wstawianego elementu * położenie nowego elementu zależy od jego wartości klucza 11. Najbardziej skomplikowaną operacją na drzewach BST jest: * usuwanie elementu * dodawanie elementu * wyszukiwanie elementu * sortowanie elementów 12. Jeżeli węzeł drzewa BST nie ma potomków lub ma 1 potomka, to usuwanie wymaga * O(n) operacji * O(h) operacji * O(1) operacji * O(log_2 n) operacji 13. Węzeł dodawany do drzewa BST zawsze jest: * następnikiem korzenia * liściem * elementem największym * elementem najmniejszym 14. Po wstawieniu elementu z do drzewa BST, left(z) i right(z) wskazują na: * element z * na samych siebie * na korzeń * mają wartość null 15. W jaki sposób należy usunąć z drzewa BST węzeł z, jeśli ma on dokładnie jednego potomka? * należy usunąć z, a potomka przypisać dowolnemu węzłowi * należy zastąpić węzeł jego następnikiem * należy usunąć z, a jego potomka zapisać jako potomka rodzica z * należy ustawić wskaźnik rodzica na null 16. Aby uzyskać posortowany ciąg elementów drzewa BST należy: * przejść po nim metodą in-order * przejść po nim metodą pre-order * przejść po nim medodą post-order * konieczne jest przetworzenie drzewa dodatkową funkcją sortującą 17. [drzewo.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą pre-order? 18. [drzewo.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą post-order? 19. [drzewo.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą in-o rder? 20. Stwórz drzewo BST z elementami o kluczach : 8, 15, 2, 14, 5, 13, 9, 10, 1 21. Stwórz drzewo BST z elementami o kluczach : 1, 2, 3, 9, 8, 7, 5, 4, 6 22. [drzewo2.png] Jak będzie wyglądało to drzewo BST po usunięciu elementu o kluczu 2? 23. [drzewo2.png] Jak będzie wyglądało to drzewo BST po usunięciu elementu o kluczu 9? 24. [drzewo2.png] Jak będzie wyglądało to drzewo BST po usunięciu elementu o kluczu 17? 25. Poprzednik x w drzewie BST to: * prawy potomek x * lewy potomek x * najmniejszy element y wśród elementów większych od x * największy element y wśród elementów mniejszych od x 26. [drzewo3.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą post-order? 27. [drzewo3.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą in-order? 28. [drzewo3.png] Poprzednikiem elementu o kluczu 7 jest element: * 6, ponieważ jest rodzicem 7 * 6, ponieważ jest największym kluczem z kluczy mniejszych od 7 * 4. ponieważ jest bratem 7 * 8, ponieważ jest korzeniem drzewa 29. Podczas budowania drzewa BST, danymi które mogą degenerować drzewo są dane: * nieposortowane * posortowane * nieujemne * w niewielkich ilościach 30. Budując drzewo BST bez założenia unikatowości kluczy należy pamiętać że: * nie może dojść do sytuacji, gdy klucz rodzica jest równy kluczowi jego potomka * elementy powtarzające się należy dowiązywać wyłącznie jako dzieci lewe * elementy powtarzające się należy dowiązywać wyłącznie jako dzieci prawe * należy samodzielnie ustalić sposób dowiązania powtarzających się elementów i konsekwentnie go przestrzegać w pracy z danym drzewem