egz AiSD 02

AiSD, egzamin - 10.02.2014

1 11 S|» Określ wszystkie zależności / e 0{g) (dla / / g) dla nadających ^l“^nMl '“•“flonyehdian > 1):njń.**■»\    „<. (wyznaczę-

nic nieprawidłowej zależności powoduje odjęcie 3 punktów).

['* ">^znac* / ^taką. że czas działania algorytmu znajduje się w G(/)-BlaBła(uu *t. int koniec)ł

suma:=0; for(i;r: | ₍₀ i=konicc/2) suma:=suma + t[ij; return suma * BlaBla(t. koniec/2); }%BlaBła

3. < i 5p) Sortowanie tablicy ,[1.7]    {5. o 3,9,,. _r} algorytmem _quick.

sort il/ielacym według ostatniego elementu tablicy, t(koniec):

QS(int *t. int początek, int koniec)! iApoczatek+l>= koniec) {

if {[[początek] > t[koniccJ) swap(t. początek, koniec): return; }

i:-partition(t, początek, koniec); swap(t, i. koniec):

QS(t.początek, i-1); QS(t. i+1, koniec); } <rQS

Wypisz drzewo wywołań rekurencyjnyeh w postaci QS(t. i. j) oraz zawartość tablicy w momencie każdego wywołania (korzeń drzewa to QStt.l,7). [5,2,8,3,9,ł,7J).

4. (15p) Wypisz kolejne drzewa BST powstałe przez wykonanie następujących operacji na pustym drzewie: i(3), i(S), i(6), i(!). i(4). ip), i( 10), dt3: (łOp). Usuwając element, który nie jest liściem wpisujemy u jego miejsce odpowiedni element z jego prawego podrzewa. Następnie, stosując rotacje przesuń element 7 do korzenia (5p).

5 i 15p > Wysokość pustego drzewa to długość jego najdłuższej ścieżki (czyli łic/ba krawędzi na tej ścieżce). Wysokość pustego drzewa (przez konwencję i to I. wysokość drzewa jednolcmcntowego to 0.

Napis/ algorytm wysokosc (node * ) . kloty wywołany dla argumentu ♦ r zwróci wysokość drzewa, na które wskazuje t ree. Przyjmij, że node jesi strukturą postaci ser uct node{int -<ey; node    node

•right;}

6. i 5p Wyszukujemy z 6 elementów o kluczach: a. b, c, d. e ,t. Prawdopodo* h|,;,.stwa wyszukiwania elementu o danym kluczu są podane w nawiasach. a<0.3n b(0.l). c(0.2), d(0.2), c(0.l). f(0.l). /buduj optymalne drzewo BST. które pozwoli zminimalizować koszt wyszukania jednego elementu (10pi. Oblicz średni koszt wyszukania elementu (czyli średnią liczbę odwiedzonych elementów) (5p). Możesz założyć, że nigdy nie są wyszukiwane elementy spoza listy.