wejsciowki, wejsciowka05, Wejściówka 5 Struktury danych


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?







Wejściówka 5

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

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

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




Wejściówka 5

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

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

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
















  1. 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ć.

  2. 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ń?

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

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



Wyszukiwarka