Wejściówka 5 Struktury danych

1. Czy następujący ciąg liczb może być ciągiem etykiet drzewa BST odczytanym w porządku inorder (tzn.: lewy, korzeń, prawy): 1,4,6,8,9,3, 5. Odpowiedź uzasadnić.

2. Utwórz drzewo BST wkładając kolejno elementy 5, 1, 4, 8, 6, 3, 9, 2
do drzewa początkowo pustego.

3. Jaki jest koszt pesymistyczny wstawienia jednego elementu do BST o n wierzchołkach?

4. Jaka jest wysokość drzewa binarnego, zawierającego 17 elementów? Podaj oszacowanie z góry i w dołu. Odpowiedź uzasadnić.

5. Do początkowo pustego drzewa BST włożono elementy 5,4,3,2,1,6,7,8. Narysuj drzewo otrzymane w wyniku.

6. Jaki jest koszt średni usunięcia jednego elementu z drzewa BST o n wierzchołkach?

7. Czy z drzewie BST wszystkie wierzchołki leżące na tym samym poziomie tworzą ciąg uporządkowany? Odpowiedź uzasadnić.

8. Z drzewa BST postaci 4
3 7
1 2 5 8
6
usunięto korzeń . Narysuj drzewo BST powstające w wyniku tej operacji.

9. Jaki jest średni koszt wyszukania 1 elementu w drzewie BST o n wierzchołkach?

10. Czy wykonanie operacji włożenia elementu e do stosu, a potem usunięcia jednego elementu zależy od kolejności ich wykonywania? Odpowiedź uzasadnić.

11. Dany losowo ciąg najpierw wkładamy kolejno do drzewa BST a potem odczytujemy etykiety tego drzewa w porządku inorder. Jaki będzie porządek elementów na wyjściu i jaki jest koszt każdego etapu tego algorytmu mierzony liczbą wykonanych porównań?

12. Podaj przykład formuły prawdziwej w dowolnej strukturze stosów i fałszywej w strukturze kolejek FIFO.

13. Która wartość jest większa w drzewie doskonałym: liczba liści czy liczba wierzchołków wewnętrznych?