Strona główna

Algorytmy I struktury danych weit uz pytania egzaminacyjne termin 0 2 luty 2011


Pobieranie 42.12 Kb.
Data18.06.2016
Rozmiar42.12 Kb.
Algorytmy i struktury danych

WEIT UZ

pytania egzaminacyjne - termin 0 2 luty 2011

imię i nazwisko, grupa : .....Ygrek Iksiński, 100 IDM.................................................




1

2

3

4

5



ocena

6

4

4

4

4

22

bdb




  1. Wyjaśnij pojęcia :

    1. stos:

Liniowa struktura danych typu LIFO (last in, first out), tzn. dostępny do edycji i do ewentualnego usunięcia jest tylko ostatnio dodany element. Zdefiniowane są tylko dwie procedury : dodania elementu na wierzch stosu i usunięcia elementu z wierzchu stosu.



    1. B-drzewo

B-drzewo rzędu m jest strukturą składającą się z węzłów mogących zawierać więcej niż jeden klucz. Dowolny węzeł, poza korzeniem, zawiera co najmniej m≤n≤2m kluczy. Klucze w węźle są posortowane rosnąco. Węzeł o n kluczach może posiadać n+1 potomków. Klucze i-tego potomka (i=0,1,..,n) są większe od i-tego klucza rodzica, a mniejsze od (i+1)-szego klucza rodzica. Struktura B-drzewa jest stosowana w organizacji pamięci zewnętrznych komputerów.


    1. drzewo AVL:

Drzewo AVL jest zmodyfikowaną wersją drzewa przeszukiwań binarnych (BST). W opisie węzła dodano dodatkowy parametr bl=hl-hr, zwany balansem, gdzie hl i hr są wysokościami odpowiednio lewego i prawego poddrzewa danego elementu. Procedury dodania i usunięcia elementu zdefiniowane są w ten sposób, aby balans dowolnego elementu |bl|≤1.



  1. Napisz procedurę szukajmax(root) szukającą elementu o największym kluczu w drzewie czerwono-czarnym o korzeniu wskazanym przez root.


Struktura ułożenia kluczy w drzewie czerwono-czarnym jest identyczna jak w drzewie przeszukiwań binarnych (BST). A zatem największy element znajduje się w skrajnie prawym elemencie drzewa. Zatem procedura wygląda tak:
function x=maxBST(root)

x=root

while x!=null

do x=r[x] % x staje się prawym potomkiem x

return x

  1. Załóżmy, że poniższa tabela przedstawia tekst i wzorzec przystawiony do jego początku:

B

C

B

B

C

D

B

D

C

A

C

B

A

D

B

B

C

B

B

C

B




























O ile pozycji w prawo zostanie przesunięty wzorzec po stwierdzeniu niezgodności, jeżeli użyjemy metody:

    1. Naiwnej (brute-and-force) : ..1..(w tej metodzie zawsze przesuwamy się o 1)

    2. Knuta-Morrisa-Pratta : ..3..(niezgodność jest na 6 pozycji, w zgodnej części wzorca BCBBC maksymalny prefiks zgodny z sufiksem jest BC, a zatem pierwsze BC musi się pokryć z końcowym BC, czyli przesuwamy o 3 pozycje)

    3. Rabina-Karpa : ..1..( lub - ; w tej przekodowanie polega na usunięciu kodu pierwszego znaku i dodaniu kodu znaku ostatniego, czyli zawsze przesuwamy się o 1)

    4. Boyera-Moore’a : ..6..(symbol D nie występuje we wzorcu, zatem przesuwamy o całą długość wzorca, czyli o 6 pozycji).



  1. Poniższą tablicę:




5

3

8

4

7

6


Przekształć do postaci stogu (kopca) zgodnie z pierwszym etapem sortowania stogowego.
Patrzymy na tablicę, jako zapis drzewa binarnego, w którym i-ty element posiada ewentualnych potomków na pozycjach 2i oraz 2i+1. Przetwarzanie powyższego drzewa zaczynamy od ostatniego elementu, który ma jeszcze potomków i iteracje będą szły do pierwszego elementu. Tym ostatnim rodzicem jest element na 3 pozycji o wartości 8, jego potomek jest na pozycji 6 o wartości 6. Ponieważ 8>6, to nic nie robimy. Przechodzimy do pozycji 2 o wartości 3, potomkowie są na pozycji 4 i 5 (o wartościach odpowiednio 4 i 7). Wybieramy większego z potomków (pozycja 5 o wartości 7. Ponieważ 3<7 następuje zamiana elementów z pozycji 2 i 5. Ponieważ pozycja 5 nie ma już potomków przechodzimy do kolejnej iteracji, tzn. do pozycji 1. Pozycja 1 (wartość 5) posiada potomków na pozycjach 2 i 3 (o wartościach odpowiednio 7 i 8) wybieramy większego z potomków (pozycja 3 – wartość 8). Ponieważ 5<8 zamieniamy elementy pozycji 1 i 3. Pozycja 3 posiada potomka na pozycji 6 o wartości 6. Ponieważ 5<6 następuje zamiana elementów pozycji 3 i 6. Ponieważ pozycja 6 nie ma już potomków, to koniec procedury. Ostateczna postać tablicy jako pierwszego stogu jest następująca:

8

7

6

4

3

5



  1. W poniższym dwukopcu usuwamy korzeń, jak będzie wyglądał dwukopiec po zakończeniu tej operacji



Usunięcie korzenia powoduje przesunięcie ostatniego elementu (dolny rząd skrajnie prawy) tzn. o wartości 1 na pozycję korzenia. Zaburzamy w ten sposób strukturę dwukopca.

























Przystępujemy do porządkowania. Potomkowie korzenia (1) mają wartości (8) i (7), wybieramy większy, ponieważ jest większy od (1) zamieniamy miejscami, czyli struktura wygląda tak





Teraz potomkami (1) są (5) i (6), większe jest (6), które jest większe od (1), zamieniamy miejscami



Teraz potomkami (1) są (3) i (0), większe jest (3), które jest większe od (1), zamieniamy miejscami




I tak powinna wyglądać ostateczna odpowiedź.


©snauka.pl 2016
wyślij wiadomość