110134

Algorytmy i struktury danych.

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

ZESTAW 1

1.    Scharakteryzuj B-drzewo (budówa strony, operacje wykonywane na drzewie i ich złożonos'ć, wady i zalety w porównaniu z innymi strukturami danych, przeznaczane drzewa.

2.    Napisz procedurę, która z uiaiporządkowanego pliku elauaitowego (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^A.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 algorynu sortowania QuickSort (zasadę działania algorynuu, cechy, przydahiość do sortowania określonych struktur danych).

6.    W tablicy haszowanej A[0.. 16) pozycję elanami o kluczu k wyznacza się ze wzoru:

H_l(k)=h(k)+h^,(k)*i gdzie h(k)=k mod 17 oraz h'(k)=k mod7.

Jaka to metoda rozstrzygania konfliktów?

Podaj indeksy elanaitów sprawdzanych przy wyszukiwaniu kluczy: x=12 i y=45 gdy: A=I17,-,Z-.4.5,23.-,-.-. 10.1229,-. 14.15.16)

UWAGA: - oznacza wolną pozycję tablicy.

ZESTAW 2

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

2.    Napisz procedurę, która w pliku elemaitowym, zawierającym rekordy opisujące osoby, zakmalizuje 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ć elauaity zawierające w polu klucz wartość mniejszą lub równą podanej wartości K, do listy drugiej pozostałe elemaity.

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

(UWAGA: głębokość korzaiia wynosi 0).

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

6.    W tablicy haszowanej A[0.. 16) pozycję elanami o kluczu k wyznacza się ze wzoru:

H,(k)=h(k)+r gdzie h(k)=k mod 17

Jaka to metoda rozstrzygania konfliktów?

Podaj indeksy elanaitów sprawdzanych przy wyszukiwaniu kluczy: x=l i y=27 gdy:

A=[17,14.2-.4,22,9,1,25,-, 13,31,-, 16)

UWAGA: - oznacza wobią pozycję tablicy.