��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 2002Przykładowe zadania na zaliczenie matematyki z semestru 1 z rozwiązaniamiTest po 6 klasie czerwiec 2002 sportZaliczenia czerwiec 2014Kolokwium zaliczeniowe sem 1 07 08 rozwiazaniaRozwiązanie Egzaminu potwierdzającego kwalifikacje zawodowe tec hnik mechanik czerwiec 2010Egzamin zawodowy praktyczny technik spedytor czerwiec 2012 (przykładowe rozwiązanie)4 zadania zaliczenia opis rozwiązaniaczerwiec2012 rozwiazania2002 czerwiecwięcej podobnych podstron