Algorytmy i struktury danych - zadania z egzaminu

Algorytmy i struktury danych.
Zadania z egzaminu (dr. J. Ratajczak & dr. K. Koleśnik)
ZESTAW 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. 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). Napisz procedurę scalającą dwie listy uporządkowane wg. pola klucz w jedną listę uporządkowaną. 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) Omów algorytm sortowania QuickSort (zasadę działania algorytmu, cechy, przydatność do sortowania określonych struktur danych). W tablicy haszowanej A[0..16] pozycję elementu o kluczu k wyznacza się ze wzoru: Hi(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 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). Napisz procedurę, która w pliku elementowym, zawierającym rekordy opisujące osoby, zaktualizuje pole adres w rekordzie osoby o podanym nazwisku. 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. 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). Omów algorytm sortowania HeapSort (cechy stogu, zasadę działania algorytmu, cechy, przydatność do sortowania określonych struktur danych). W tablicy haszowanej A[0..16] pozycję elementu o kluczu k wyznacza się ze wzoru: Hi(k)=h(k)+i2 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. ... zobacz całą notatkę