Egzamin 2010 grupa A

1) Zbudiwać drzewa BST o wysokościach k=2,3,4, będące hierarchiczną strukturą zbioru kluczy {5,7,9,11,13,15}.

a) Podać algorytmy trawersowania drzewa BST według inorder, preorder. Dla wybranego drzewa wyprowadzić kolejność zgodnie z napisanymi algorytmami.

b) Przedstawić w trzech dowiązaniowych reprezentacjach wybrane z utworzonych drzew.

c) Podać i uzasadnić złożoność obliczeniową algorytmów interfejsu dla zbudowanych struktur drzewiastych

2) Porównać algorytmy sortowania „Quick Sort” i „Merge Sort” pod względem złożobości obliczeniowej (czasowej, pamieciowej) i stabilności. Określić najbardziej korzystny oraz niekorzystny dla każdego z nich zestaw danych.

3) Wymienić własności drzew czerwono-czarnych RB. Zbudować algorytm interfejsu drzewa RB umożliwiający wybór wierzchołka o maksymalnej wartości klucza. Podać operacje na drzewie które zmieniają jego strukturę oraz oszacować ich złożoność.

4) Oszacować wg notacji asymptotycznej tempo wzrostu T(n) będącej rozwiązaniem równania rekurencyjnego T(n) = T(n/2)+2 dla n>1 oraz T(1)=1 dla n=1

5) Wpisać swoje literowe nazwisko do n elementowej tablicy znakowej H (litery małe i duże są nierozróżnialne). Zbudować kopiec z znaków nazwiska (założyć porządek kodów znaków zgodny z porządkiem alfabetycznym). Zmodyfikować tablicę H, tak aby była implementacją utworzonego kopca.

6) Przedstaw problem grupowania (************) występujący w wyszukiwaniu z haszowaniem. Zaproponuj sposób jego rozwiązania.

7) Dana jest jednokierunkowa lista w implementacji dowiązaniowej.

a) Wyznaczyć adres elementu o maksymalniej wartości max

b) Zmodyfikować daną listę tak, aby pozostały na niej tylko elementy o wartościach mniejszych od max/2. Na koniec tej listy wstawić element o wartości max.

c) Z otrzymanej listy utworzyć listę cykliczną.

8) Zbudować rekurencyjny algorytm sortowania przez wybór (selection_sort).

a) Podać postać równania rekurencyjnego dla struktury algorytmu

b) Oszacować złożoność obliczeniową algorytmu (rozważyć równanie)