ASD e 02 2003 2

13a. Narysuj kopiec-drzewo otrzymane w wyniku kolejnego wkładania elementów 5,4,2.6,7,0,1. 13b. Ile porównań trzeba wykonać aby usunąć korzeń tego drzava?

14a. Wypisz wierzchołki drzewa z zadania 13 zgodnie z kolejnością ich odwiedzania metodą „najpierw w głą^ BFS.

14b. Jakiej struktury pomocniczej używa algorytm BFS?

15. Który z poniższych ciągów nie przedstawia ciągu etykiet węzłów, odwiedzaiych w trakcie sprawdzania, czy liczba 316 jest etykietą drzewa BST (wierzchołki przeglądamy zgodnie z algorytmem member w drzewach binarnych poszukiwań)? Zaznacz błędne etykiety. lSa. 8, 12. 499, 250, 500,363, 280, 316 15b. 4,444. 44, 88, 188,488, 200, 316

I6a. Wypisz stosowną kolejkę krawędzi i narysuj minimalne drzewo rozpinające otrzymane w wyniku zastosowania algorytmu Kruskala do podanego obok grafu G.

16b. Czy. jeśli wagi wszystkich krawędzi są takie same, to dowolne drzewo rozpinające ma kosź minimalny?

17a. W pewnym tekście występują tylko litery A, I, O, S, Z a ich częstości występowania wynoszą A-17,1-6, 0-5, S-4, Z-3. Zbuduj drzewo kodowe Huffmana.

17b.Odkoduj przy pomocy otrzymanego kodu tekst „ 1001101011110”.

18a. Wypisz kolejność w jakiej akceptowane są krawędzie w algorytmie Dijkstry znajdowania najkrótszych ścieżek od źródła A do wszystkich wierzchołków grafu z zadania 16.

18b. Jaki byłby koszt rozwiązania problemu najkrótszych ścieżek, gdyby zastosować algorytm naiwny badania wszystkich możliwych ścieżek w grafie?

\

19a. Co robi następujący algorytm działający w strukturze kolejek priorytetowych { s:=0; while not empty(x) do s := s+min(x); x:= dełmin(x); od: wypisz(s)}?

19b. Załóżmy, że kolejka priorytetowa jest reprezentowana przez drzewo BST. Oszacuj wysokość tego drzewa po wykonaniu pierwszych n/2 iteracji powyższym algorytmem, jeśli w kolejce było na początku n=2^k elementów?

20 Napisz funkcję, która bez użycia zmiennych globalnych i pętli znajduje sumę wszystkich elementów danej n elementowej tablicy tab, n>0.