wejsciowki, wejsciowka05.html, 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?

  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?

  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

Podobne podstrony:
wejsciowki, wejsciowka05, Wejściówka 5 Struktury danych
Algorytmy i struktury danych Wykład 1 Reprezentacja informacji w komputerze
Algorytmy i struktury danych Wykład 3 i 4 Tablice, rekordy i zbiory
Algorytmy i struktury danych, AiSD C Lista04
Algorytmy i struktury danych 08 Algorytmy geometryczne
Instrukcja IEF Algorytmy i struktury danych lab2
Algorytmy, struktury danych i techniki programowania wydanie 3
Algorytmy i struktury danych 1
Cw 5 Struktury Danych Materiały dodatkowe
Ściaga sortowania, algorytmy i struktury danych
ukl 74xx, Informatyka PWr, Algorytmy i Struktury Danych, Architektura Systemów Komputerowych, Archit
cw 0 1, pwr, informatyka i zarządzanie, Informatyka, algorytmy i struktury danych
AIDS w7listy, studia, Semestr 2, Algorytmy i struktury danych AISD, AIDS
lab3 struktury danych
k balinska projektowanie algorytmow i struktur danych
W10seek, studia, Semestr 2, Algorytmy i struktury danych AISD, AIDS
ALS - 001-000 - Zadania - ZAJECIA, Informatyka - uczelnia, WWSI i WAT, wwsi, SEM II, Algorytmy i Str

więcej podobnych podstron