plik


��ALGORYTMY I STRUKTURY DANYCH (zaliczenie semestru letniego 2001/2002  rok I - grupa A) Odpowiedzi: Zad.1. B C A D F E Macierz incydencji: A B C D E F A - 1 0 0 0 0 B 1 - 1 0 0 0 C 0 0 - 0 0 0 D 1 0 0 - 1 0 E 0 0 0 1 - 1 F 1 0 1 0 0 - Lista w wektorze z warto[ciowaniem wektora: Val. 1 A B 2 B A C 0 C 2 D A E 2 E D F 2 F A C Zad.2. C moc (TA ) = 2 moc ( T ) = 2 3 = 8 moc (T1 ) = moc (TA ) * moc (TB ) * moc (TD ) = 8 * 3 * 5 = 120 moc (T2 ) = moc (T1 ) 5 = 120 5 Zad.3. A B C D E F G H J K L M Nastpnik wzBa A N Po usuniciu wzBa A i rekonstrukcji BST: K B C D E F G H J N L M Zad.4. Aczenie H1 i H2 Lista: 5 19 12 7 15 11 3 2 10 4 5 2 3 Kolejne fazy Bczenia drzew dwumianowych: 5 19 7 15 10 12 3 2 4 5 11 2 3 Kopiec H12: 5 19 15 10 7 12 3 2 4 5 11 2 3 Aczenie H12 i H3 Lista i ostateczna konfiguracja kopca dwumianowego H: 6 19 5 15 5 10 7 12 3 2 4 5 11 2 3 Zad.5. Maksymalna liczba wzB�w Nd(k), kt�re mo|na umie[ci na k poziomach drzewa rzdu d, wynosi: - N (k) = = 1+ d + d + ... + d - "d = Maksymalna liczba kluczy dla ka|dego wzBa wynosi (d 1). Dla drzewa binarnego d = 2. Z ka|dym wzBem mo|e by zwizany co najwy|ej 1 klucz. Std zale|no[ci: Liczba poziom�w Maksymalna liczba wzB�w Maksymalna liczba kluczy 1 1 1 2 1+2=3 3 3 3+4=7 7 4 7+8=15 15 5 15+16=31 31 6 31+32=63 63 Liczba poziom�w obsadzonych przez wzBy skojarzone z 63 rekordami bazy danych, kt�rych lokalizacja zale|y od skBadowej rekordu przyjtej jako klucz, w doskonale wywa|onym drzewie binarnym wynosi k2 = 6. Dla drzewa rzdu 5-tego d = 5. Z ka|dym wzBem mog by zwizane co najwy|ej 4 klucze. Std zale|no[ci: Liczba poziom�w Maksymalna liczba wzB�w Maksymalna liczba kluczy 1 1 4 2 1+5=6 24 3 6+25=31 124 Liczba poziom�w obsadzonych przez wzBy skojarzone z 63 rekordami bazy danych, kt�rych lokalizacja zale|y od skBadowej rekordu przyjtej jako klucz, w doskonale zr�wnowa|onym drzewie rzdu 5-tego wynosi k5 = 3. Stosunek liczby poziom�w obu struktur: k 6 = = 2 k 3 Zad.6. Stan pocztkowy: 1 3 5 9 7 8 6 4 2 PodziaBy: 1 3 5 9 7 8 6 4 2 1 3 5 9 7 8 6 4 2 1 3 5 9 7 8 6 4 2 1 3 5 9 7 8 6 4 2 1 3 Scalanie: 1 3 1 3 5 7 9 6 8 2 4 1 3 5 7 9 2 4 6 8 1 2 3 4 5 6 7 8 9 Zad.7. Suma czsto[ci dla wszystkich znak�w wynosi: 64+4+32+74+8+2+16=200 1-szy podziaB: 0 - {A, B, C} (Bczna czsto[ wzgldna =64+4+32=100) ____________________________________________________ 1  {D, E, F, G} (Bczna czsto[ wzgldna =74+8+2+16=100) 2-gi podziaB: 00 - {A} (czsto[ wzgldna =64) __________________________________________________ 01 - { B, C} (Bczna czsto[ wzgldna =4+32=36) ____________________________________________________ 10  {D } (czsto[ wzgldna =74) __________________________________________________ 11  {E, F, G} (Bczna czsto[ wzgldna =8+2+16=26) 3-ci podziaB: 010 - {B} (czsto[ wzgldna =4) __________________________________________________ 011 - {C} (czsto[ wzgldna =32) ____________________________________________________ 110  {E, F} (Bczna czsto[ wzgldna =8+2=10) __________________________________________________ 111 - {G} (czsto[ wzgldna =16) 4-ty podziaB: 1100 - {E} (czsto[ wzgldna =8) __________________________________________________ 1101 - {F} (czsto[ wzgldna =2) Ostateczna tabela kod�w binarnych: x A B C D E F G kod 00 010 011 10 1100 1101 111 UWAGA: Dopuszczalne s inne rozwizania, wynikajce z arbitralnych decyzji, kt�remu z dw�ch podzbior�w przyporzdkowa bit o warto[ci 1, a kt�remu bit o warto[ci 0 (nie zmienia to faktu, |e ostateczny kod musi by kodem przedrostkowym, za[ dBugo[ci cig�w binarnych przyporzdkowanych poszczeg�lnym znakom alfabetu powinny by takie, jak w powy|szej tabeli). Zad.8. Nale|y obliczy 5 18 mod 7. n = 7 a = 5 k = 18 = 1 . 2 4 + 0 . 2 3 +0 . 2 2 + 1 . 2 1 + 0 . 2 0 Kroki wstpne: b = 1 k `" 0 x = 5 k 0 `" 1 Kolejne iteracje: i = 1 x = 5 2 mod 7 = 25 mod 7 = 4 k 1 = 1 b = 4 . 1 mod 7 = 4 i = 2 x = 4 2 mod 7 = 16 mod 7 = 2 k 2 = 0 i = 3 x = 2 2 mod 7 = 4 mod 7 = 4 k 3 = 0 i = 4 x = 4 2 mod 7 = 16 mod 7 = 2 k 4 = 1 b = 2 . 4 mod 7 = 1 Odpowiedz: 5 18 mod 7 = 1 UWAGA: Rozwizanie premiowane 2-ma punktami (stosujce twierdzenie Fermata-Eulera) jest nastpujce: �(7) = 6 5 18 mod 7 = 5 3*�(7) mod 7 = (5 �(7))3 mod 7 = 1 3 mod 7 = 1 Zad.9. Konfiguracja kopca binarnego o 4-ch wzBach: Dla czterech r�|nych warto[ci kluczy istnieje 4! = 24 r�znych przyporzdkowaD kluczy wzBom. Korzeniem mo|e by wyBcznie wzeB o najwikszej warto[ci klucza (czyli wzeB z kluczem 24). Pozostaje zatem 3! = 6 mo|liwo[ci. Jego prawym potomkiem mo|e by wzeB z kluczem o warto[ci r�wnej ka|dej z pozostaBych trzech mo|liwych. Ale w�wczas uporzdkowanie pozostaBych dw�ch wzB�w w prawym poddrzewie korzenia jednoznacznie wynika z porzdku kopcowego. Wniosek: z 4-ch wzB�w o podanych warto[ciach kluczy mo|na utworzy tylko 3 r�|ne kopce binarne zorientowane na maksimum: 24 24 13 21 7 21 7 13 24 21 13 7 Zad.10. Liczba element�w Z 13 : | Z 13 | = � (13) = 12 Liczba generator�w: � (� (13)) = � (12) = � (22 *3 ) = 1 1 1 2 ����1 ��. = 12 * * = 4 12��1 - ���� - �� �� 2 3 2 3 �� ���� �� 41 42 43 44 45 46 4 3 12 9 10 1 Liczba 4 nie jest generatorem Z 13. Reszt kwadratowych w Z jest � (12) / 2 = 6. Trzy elementy Q13 ju| s 13 znane (1, 3, 9). Do wyznaczenia pozostaBych pozostaje metoda  pr�b i bBd�w albo wyznaczenie jednego z 4-ch generator�w i jego parzystych potg. Sprawdzmy, czy liczba 2 jest generatorem grupy multiplikatywnej Z*13. 21 22 23 24 25 26 27 28 29 210 211 212 2 4 8 3 6 12 11 9 5 10 7 1 Liczba 2 jest generatorem Z 13. A zatem zbi�r reszt kwadratowych w Z 13 to Q 13 = {1, 3, 4, 9, 10, 12}. ALGORYTMY I STRUKTURY DANYCH (zaliczenie semestru letniego 2001/2002  rok I - grupa B) Odpowiedzi: Zad.1. B C A D F E Macierz incydencji: A B C D E F A - 1 0 0 0 0 B 0 - 1 0 0 0 C 0 0 - 1 0 0 D 1 0 0 - 0 0 E 0 1 0 1 - 1 F 1 0 0 0 0 - Lista w wektorze z warto[ciowaniem wektora: Val. 1 A B 1 B C 1 C D 1 D A 3 E B D F 1 F A Zad.2. moc (TA ) = moc (TB ) * moc (TC ) * moc (TD ) = 3 * 3 * 5 = 45 moc (T1 ) = 2 moc ( TA ) = 2 45 moc (T2 ) = moc (TA ) 5 = 45 5 Zad.3. A B C D E F G H J K L M Nastpnik wzBa B N Po usuniciu wzBa B i rekonstrukcji BST: A J C D E F G H K L M N Zad.4. Aczenie H1 i H2 Lista: 5 12 19 7 15 10 4 5 3 2 3 1 Kolejne fazy Bczenia drzew dwumianowych: 12 19 7 15 10 5 4 5 3 2 3 1 19 7 15 10 12 4 5 3 2 3 1 5 Kopiec H12: 15 19 3 2 7 10 12 1 4 5 5 3 Aczenie H12 i H3 Lista i ostateczna konfiguracja kopca dwumianowego H: 8 15 6 19 5 3 2 7 10 12 1 4 5 5 3 Zad.5. Maksymalna liczba wzB�w Nd(k), kt�re mo|na umie[ci na k poziomach drzewa rzdu d, wynosi: - N (k) = = 1+ d + d + ... + d - "d = Maksymalna liczba kluczy dla ka|dego wzBa wynosi (d 1). Dla drzewa binarnego d = 2. Z ka|dym wzBem mo|e by zwizany co najwy|ej 1 klucz. Std zale|no[ci: Liczba poziom�w Maksymalna liczba wzB�w Maksymalna liczba kluczy 1 1 1 2 1+2=3 3 3 3+4=7 7 4 7+8=15 15 5 15+16=31 31 6 31+32=63 63 7 63+64=127 127 Liczba poziom�w obsadzonych przez wzBy skojarzone z 100 rekordami bazy danych, kt�rych lokalizacja zale|y od skBadowej rekordu przyjtej jako klucz, w doskonale wywa|onym drzewie binarnym wynosi k2 = 7. Dla drzewa rzdu 3-tego d = 3. Z ka|dym wzBem mog by zwizane co najwy|ej 2 klucze. Std zale|no[ci: Liczba poziom�w Maksymalna liczba wzB�w Maksymalna liczba kluczy 1 1 2 2 1+3=4 8 3 4+9=13 26 4 13+27=40 80 5 40+81=121 242 Liczba poziom�w obsadzonych przez wzBy skojarzone z 100 rekordami bazy danych, kt�rych lokalizacja zale|y od skBadowej rekordu przyjtej jako klucz, w doskonale zr�wnowa|onym drzewie rzdu 3-ego wynosi k3 = 5. Stosunek liczby poziom�w obu struktur: k 7 = = 1,4 k 5 Zad.6. Stan pocztkowy tablicy A[ ]: 7 7 1 3 1 2 4 7 8 Przyjto NMAX =8. Tablica C[ ] po pierwszej cz[ci zliczania: 2 1 1 1 0 0 3 1 Tablica C[ ] po drugiej cz[ci zliczania (przyrostowego): 2 3 4 5 5 5 8 9 Wstawianie do tablicy wynikowej B[ ]: A[9]=8 B C 8 2 3 4 5 5 5 8 8 A[8]=7 B C 7 8 2 3 4 5 5 5 7 8 A[7]=4 B C 4 7 8 2 3 4 4 5 5 7 8 A[6]=2 B C 2 4 7 8 2 2 4 4 5 5 7 8 A[5]=1 B C 1 2 4 7 8 1 2 4 4 5 5 7 8 A[4]=3 B C 1 2 3 4 7 8 1 2 3 4 5 5 7 8 A[3]=1 B C 1 1 2 3 4 7 8 0 2 3 4 5 5 7 8 A[2]=7 B C 1 1 2 3 4 7 7 8 0 2 3 4 5 5 6 8 A[1]=7 B C 1 1 2 3 4 7 7 7 8 0 2 3 4 5 5 5 8 Zad.7. Lista znak�w po uporzdkowaniu zgodnie z rosnc czsto[ci: {F}  31 {D}  25 {C}  12 {G}  11 {A}  10 {B}  8 {E}  1 po 1-ym kroku: {F}  31 {D}  25 {C}  12 {G}  11 {A}  10 {B, E}  9 {B} �! [...1], {E}�! [...0] po 2-im kroku: {F}  31 {D}  25 {C}  12 {G}  11 {A, B, E}  19 {A} �! [...1], {B} �! [...01], {E}�! [...00] po 3-im kroku: {F}  31 {D}  25 {C, G}  23 {C} �! [...1], {G}�! [...0] {A, B, E}  19 {A} �! [...1], {B} �! [...01], {E}�! [...00] po 4-ym kroku: {F}  31 {D}  25 {C, G, A, B, E }  42 {C} �! [...11], {G}�! [...10], {A} �! [...01], {B} �! [...001], {E}�! [...000] po 5-ym kroku: {F, D}  56 {F} �! [...1], {D}�! [...0] {C, G, A, B, E }  42 {C} �! [...11], {G}�! [...10], {A} �! [...01], {B} �! [...001], {E}�! [...000] po ostatnim 6-ym kroku: {F} �! [11], {D}�! [10], {C} �! [011], {G}�! [010], {A} �! [001], {B} �! [0001], {E}�! [0000] Ostateczna tabela kod�w binarnych: x A B C D E F G kod 001 0001 011 10 0000 11 010 UWAGA: Dopuszczalne s inne rozwizania, wynikajce z arbitralnych decyzji, kt�remu z dw�ch podzbior�w przyporzdkowa bit o warto[ci 1, a kt�remu bit o warto[ci 0 (nie zmienia to faktu, |e ostateczny kod musi by kodem przedrostkowym, za[ dBugo[ci cig�w binarnych przyporzdkowanych poszczeg�lnym znakom alfabetu powinny by takie, jak w powy|szej tabeli). Kroki wiodce do uzyskania ostatecznego kodu Huffmana mog by przedstawione w formie graficznej ilustrujcej tworzenie drzewa Huffmana. Zad.8. Nale|y obliczy 5 17 mod 6. n = 6 a = 5 k = 17 = 1 . 2 4 + 0 . 2 3 +0 . 2 2 + 0 . 2 1 + 1 . 2 0 Kroki wstpne: b = 1 k `" 0 x = 5 k 0 = 1 b = 5 Kolejne iteracje: i = 1 x = 5 2 mod 6 = 25 mod 6 = 1 k 1 = 0 i = 2 x = 1 2 mod 6 = 1 mod 6 = 1 k 2 = 0 i = 3 x = 1 2 mod 6 = 1 mod 6 = 1 k 3 = 0 i = 4 x = 1 2 mod 6 = 1 mod 6 = 1 k 4 = 1 b = 1 . 5 mod 6 = 5 Odpowiedz: 5 17 mod 6 = 5 UWAGA: Rozwizanie premiowane 2-ma punktami (stosujce twierdzenie Fermata-Eulera) jest nastpujce: �(6) = �(2) * �(3) = 1 * 2 = 2 5 17 mod 7 = 5 8*�(6)+1 mod 7 = (5 �(6)) 8 * 5 1 mod 7 = 1 8 * 5 1 mod 7 = 5 Zad.9. Ka|dy z czterech wzB�w mo|e by korzeniem drzewa BST. Je|eli korzeniem jest wzeB o najwikszej warto[ci klucza, to jego lewe poddrzewo zawiera wszystkie pozostaBe wzBy. Korzeniem tego poddrzewa mo|e by ka|dy z trzech pozostaBych wzB�w. W przypadku, gdy jest to wzeB o  [rodkowej warto[ci klucza, istnieje tylko jedna mo|liwo[ lokalizacji pozostaBych wzB�w (musz by odpowiednio: lewym i prawym potomkiem). W przypadku, gdy jest to wzeB o najwikszej lub najmniejszej warto[ci klucza spo[r�d wzB�w r�|nych od korzenia drzewa, pozostaj dwie mo|liwo[ci skonfigurowania pozostaBych dw�ch wzB�w jako pary  rodzic  potomek . Razem: 5 mo|liwo[ci.  Lustrzany przypadek dotyczy sytuacji, gdy korzeniem drzewa BST jest wzeB o najmniejszej warto[ci klucza. Je|eli korzeniem jest wzeB o drugiej w kolejno[ci zgodnej z uporzdkowaniem drzewa BST warto[ci klucza, to jego lewe poddrzewo zawiera tylko wzeB o najmniejszej warto[ci klucza, za[ prawy  dwa pozostaBe wzBy, co umo|liwia utworzenie tylko 2 r�|nych drzew BST.  Lustrzany przypadek dotyczy sytuacji, gdy korzeniem drzewa BST jest wzeB o 3-ej w kolejno[ci warto[ci klucza.  KBania si rekurencja !!! W sumie r�|nych mo|liwych drzew jest: 5+5+2+2=14. Poni|ej przedstawiono graficznie ich konfiguracje. 12 12 12 9 9 6 6 3 12 3 9 6 12 3 3 3 6 9 9 6 3 3 3 9 6 6 6 12 12 9 3 9 3 12 12 12 6 9 9 6 6 6 9 12 3 3 12 9 9 9 3 6 12 12 6 3 Zad.10. Liczba element�w Z 11 : | Z 11 | = � (11) = 10 Liczba generator�w: � (� (11)) = � (10) = � (2 *5 ) = 1 1 1 4 ����1 ��. = 10 * * = 4 10��1 - ���� - �� �� 2 5 2 5 �� ���� �� Sprawdzmy, czy liczba 2 jest generatorem grupy multiplikatywnej Z*13. 21 22 23 24 25 26 27 28 29 210 2 4 8 5 10 9 7 3 6 1 Liczba 2 jest generatorem Z 11. A zatem zbi�r reszt kwadratowych w Z 11 to Q 11 = {1, 3, 4, 5, 9}.

Wyszukiwarka

Podobne podstrony:
ZALICZENIE CZERWIEC 2002
Przykładowe zadania na zaliczenie matematyki z semestru 1 z rozwiązaniami
Test po 6 klasie czerwiec 2002 sport
Zaliczenia czerwiec 2014
Kolokwium zaliczeniowe sem 1 07 08 rozwiazania
Rozwiązanie Egzaminu potwierdzającego kwalifikacje zawodowe tec hnik mechanik czerwiec 2010
Egzamin zawodowy praktyczny technik spedytor czerwiec 2012 (przykładowe rozwiązanie)
4 zadania zaliczenia opis rozwiązania
czerwiec2012 rozwiazania
2002 czerwiec

więcej podobnych podstron