Algorytmy i struktury danych.

Zadania z egzaminu (dr. J. Ratajczak & dr. K. Koleśnik)

ZESTAW 1

1. Scharakteryzuj B-drzewo (budowa strony, operacje wykonywane na drzewie i ich złożoność, wady i zalety w porównaniu z innymi strukturami danych, przeznaczenie drzewa.

2. Napisz procedurę, która z nieuporządkowanego pliku elementowego (np. pliku książek) usunie rekord o podanym kluczu (np. rekord książki o podanym numerze).

3. Napisz procedurę scalającą dwie listy uporządkowane wg. pola klucz w jedną listę uporządkowaną.

4. Napisz procedurę wpisującą do każdego węzła x (pole x^.węzły), drzewa binarnego o korzeniu k, liczbę węzłów w poddrzewie, którego korzeniem jest x.
   (UWAGA: liczba węzłów dla liścia wynosi 1)

5. Omów algorytm sortowania QuickSort (zasadę działania algorytmu, cechy, przydatność do sortowania określonych struktur danych).

6. W tablicy haszowanej A[0..16] pozycję elementu o kluczu k wyznacza się ze wzoru:
   H_i(k)=h(k)+h'(k)*i gdzie h(k)=k mod 17 oraz h'(k)=k mod 7.
   Jaka to metoda rozstrzygania konfliktów?
   Podaj indeksy elementów sprawdzanych przy wyszukiwaniu kluczy: x=12 i y=45 gdy:
   A=[17,-,2,-,4,5,23,-,-,-,10,12,29,-,14,15,16]
   UWAGA: - oznacza wolną pozycję tablicy.

ZESTAW 2

1. Scharakteryzuj drzewo AVL (budowa węzła, definicję drzewa AVL, operacje wykonywane na drzewie i ich złożoność, wady i zalety w porównaniu z innymi strukturami danych, przeznaczenie drzewa).

2. Napisz procedurę, która w pliku elementowym, zawierającym rekordy opisujące osoby, zaktualizuje pole adres w rekordzie osoby o podanym nazwisku.

3. Napisz procedurę, która podzieli listę rekordów na dwie listy (niszcząc listę początkową). Do listy pierwszej należy dołączyć elementy zawierające w polu klucz wartość mniejszą lub równą podanej wartości K, do listy drugiej pozostałe elementy.

4. Napisz procedurę wpisującą do każdego węzła x (pole x^.głęb), drzewa binarnego o korzeniu k jego głębokość (odległość węzła x od korzenia k).
   (UWAGA: głębokość korzenia wynosi 0).

5. Omów algorytm sortowania HeapSort (cechy stogu, zasadę działania algorytmu, cechy, przydatność do sortowania określonych struktur danych).

6. W tablicy haszowanej A[0..16] pozycję elementu o kluczu k wyznacza się ze wzoru:
   H_i(k)=h(k)+i² gdzie h(k)=k mod 17
   Jaka to metoda rozstrzygania konfliktów?
   Podaj indeksy elementów sprawdzanych przy wyszukiwaniu kluczy: x=1 i y=27 gdy:
   A=[17,14,2,-,4,22,-,-,-,9,1,25,-,13,31,-,16]
   UWAGA: - oznacza wolną pozycję tablicy.

---