Zdj 0002

f

i

%

' -

4

i

____ Algorytmy i Struktury Danych

EGZAMIN 2    25. 06. 2008 sem. II

TEMAT 1

Przedstawić równania rekurencyjne stosowane w analizie złożoności.

Podać przykłady algorytmów, których czasy działania spełniają te równania.

Przedstawić metodykę rozwiązania tych równań.

TEMAT 2

Omówić trzy Abstrakcyjne Typy Danych: Stos, Kolejka, Lista.

Podać algorytmy (w C lub pseudojęzyku) realizujące standardowe funkcje Stosu i Kolejki.

Podać i omówić algorytmy usuwania ze środka i wstawiania w środek listy węzła. Przedyskutować złożoność obliczeniową algorytmów korzystających z w/wym struktur.

Przedstawić algorytm prezentujący zastosowanie stosu.

TEMAT 3

Omówić tematykę, której przedstawicielem jest problem Hetmanów.

Przedstawić algorytm Hetmana, omówić struktury danych, z których korzysta.

Podać zawartości w/wym struktur danych dla przykładowych ustawień Hetmana.

Przedyskutować złożoność obliczeniową.

TEMAT 4

Omówić potencjalne problemy w grafach z wagami ujemnymi, przykłady.

Przedstawić algorytm przeszukiwania grafu w głąb DFS i zilustrować go na przykładzie grafu spójnego (9 węzłów i 14 krawędzi). Wyjaśnić pojęcie etykiety czasowe w grafie.

Przeanalizować złożoność obliczeniową.

TEMAT 5

Omówić kopiec Fibonacciego, podać stosowne przykłady, podać strukturę węzła.

Omówić algorytm zmniejszania wartości klucza (wszystkie aspekty).

Zilustrować go na przykładzie kopca z czterema węzłami na liście korzeni, gdy klucz zmniejszany znajduje się w węźle o stopniu^.

Przedyskutować problematykę złożoności obliczeniowej kopca Fibonacciego.

Zadanie I , Podać kod w języku C lub pseudokodzie, który łączy zawartość dwóch stosów, tworząc jeden wg schematu na rysunku.	1	14		14 13 12 11
Zadanie 2 i0 dla n = 1 I	-M ^2 1 ^1.....i	13 12 ~ 11“	1 1	3 '2 F
Rozwiązać równanie: T(«) ~ • 2 1— 1) -4— dla /!>l