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=2k 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.
Wyszukiwarka
Podobne podstrony:
ASD e 02 2003 1 Algorytmy i struktury danych Egzamin II rok PJWSTK, 10 luty 2003 Grupa B Nazwisko &
ASD e 02 2005 4 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko...............................
ASD e 02 2006 1 WERSJAALGORYTMY I STRUKTURY DANYCH studia dzienne, egzamin 3 luty 2006 vstkie odpow
ASD e 02 2006 3 I • u Ic l .Limu air
ASD e 02 2005 2 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 6 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2006 2 .....a *,. . — *■ *........I.iiUl.y Nmv.n
ASD e 02 2006 4 ■ *«fw IftiĄ fttdfHf AĘ -&2WmiA<TAWU
ASD e 02 2005 1 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko...............................
ASD e 02 2005 3 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 4 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko...............................
ASD e 02 2005 5 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
ASD e 02 2005 7 Egzamin ASD Studia dzienne, 7go lutego 2005 Nazwisko Nr studenta............Nr grup
więcej podobnych podstron