ALGORYTMY I STRUKTURY DANYCH
(zaliczenie semestru letniego 2001/2002  rok I - grupa A)
Skala ocen:
punkty ocena
[5,0  5,99 ) Ô! 3,0
[6,0  6,99 ) Ô! 3,5
[7,0  7,99 ) Ô! 4,0
[8,0  8,99 ) Ô! 4,5
[9,0  ) Ô! 5,0
1. Dla poniższego grafu skierowanego utworzyć macierz incydencji oraz listę
w wektorze z wartościowaniem wektora (LAVA).
B
C
A
D
F
E
2. Zdefiniowano trzy złożone typy danych: TA , T1 i T2 :
type TA = set of TC ;
type T1 = record s1 : TA ;
s2 : TB ;
s3 : TD ;
end;
type T2 = array [0...4] of T1 ;
moc (TB ) = 3 moc (TC ) = 3 moc (TD ) = 5
Obliczyć moce typów danych TA, T1 i T2.
3. Z poniższego drzewa BST usunięto korzeń (węzeł A). Przyjmując, że
algorytm rekonstrukcji drzewa po usunięciu węzła z dwoma potomkami
wymaga odpowiedniego przemieszczenia węzła będącego następnikiem
(successor) usuwanego węzła, wskazać ten węzeł (successor) oraz pokazać
drzewo BST po rekonstrukcji.
A
B C
D E F G
H J K L M
N
4. Poniższe kopce dwumianowe H1, H2 i H3 połączono w jeden kopiec
dwumianowy H, najpierw łącząc kopce H1 i H2 w kopiec H12, a następnie
łącząc kopce H12 i H3. Pokazać kolejne fazy tworzenia kopca H (włącznie z
kolejnymi fazami przekształcania odpowiednich list zawierających drzewa
dwumianowe).
5 19 7
H1:
10 4 5
H3:
6
12 15
H2:
3
5
VERTE !!!
11 3 2
2
5. 63 rekordy bazy danych umieszczono raz w doskonale wyważonym drzewie
binarnym, a raz w doskonale zrównoważonym drzewie rzędu 5-tego. Jaki jest
stosunek liczby poziomów obu struktur ?
6. Poniższą tablicę należy posortować tak, by w miejscu o indeksie 1 znalazł się
element najmniejszy, w miejscu o indeksie 2  drugi z kolei zgodnie z relacjÄ…
mniejszości, itd. Należy zastosować metodę  sortowania przez scalanie
( merge sort ). Pokazać (graficznie) wszystkie fazy sortowania.
indeks 1 2 3 4 5 6 7 8 9
wartość 1 3 5 9 7 8 6 4 2
7. Dla 7-znakowego alfabetu, o częstościach względnych występowania
poszczególnych znaków podanych poniżej, wyznaczyć kody binarne
Shannona-Fano.
x A B C D E F G
F(x) 64 4 32 74 8 2 16
8. Stosując algorytm potęgowania modulo wykorzystujący binarną
reprezentację wykładnika obliczyć 5 18 mod 7. UWAGA: Pokazać wszystkie
obliczenia dokonywane w każdej  pętli algorytmu.
9. Ile różnych kopców binarnych zorientowanych na maksimum można
utworzyć z 4-ch węzłów o wartościach kluczy 7, 13, 21 i 24 ? Pokazać w formie
graficznej konfiguracje tych kopców.
10. Ile elementów należy do grupy multiplikatywnej Z*13 ? Ile ta grupa ma
generatorów ? Czy liczba 4 jest generatorem tej grupy (odpowiedz
potwierdzić
odpowiednimi obliczeniami) ? Wyznaczyć reszty kwadratowe należące do tej
grupy multiplikatywnej.
ALGORYTMY I STRUKTURY DANYCH
(zaliczenie semestru letniego 2001/2002  rok I - grupa B)
Skala ocen:
punkty ocena
[5,0  5,99 ) Ô! 3,0
[6,0  6,99 ) Ô! 3,5
[7,0  7,99 ) Ô! 4,0
[8,0  8,99 ) Ô! 4,5
[9,0  ) Ô! 5,0
1. Dla poniższego grafu skierowanego utworzyć macierz incydencji oraz listę
w wektorze z wartościowaniem wektora (LAVA).
B
C
A
D
F
E
2. Zdefiniowano trzy złożone typy danych: TA , T1 i T2 :
type TA = record s1 : TB ;
s2 : TC ;
s3 : TD ;
end;
type T1 = set of TA ;
type T2 = array [0...4] of TA ;
moc (TB ) = 3 moc (TC ) = 3 moc (TD ) = 5
Obliczyć moce typów danych TA, T1 i T2.
3. Z poniższego drzewa BST usunięto węzeł B. Przyjmując, że algorytm
rekonstrukcji drzewa po usunięciu węzła z dwoma potomkami wymaga
odpowiedniego przemieszczenia węzła będącego następnikiem (successor)
usuwanego węzła, wskazać ten węzeł (successor) oraz pokazać drzewo BST po
rekonstrukcji.
A
B C
D E F G
H J K L M
N
4. Poniższe kopce dwumianowe H1, H2 i H3 połączono w jeden kopiec
dwumianowy H, najpierw łącząc kopce H1 i H2 w kopiec H12, a następnie
łącząc kopce H12 i H3. Pokazać kolejne fazy tworzenia kopca H (włącznie z
kolejnymi fazami przekształcania odpowiednich list zawierających drzewa
dwumianowe).
5 19 7
H1:
10 4 5
H3:
12 15 8
H2: 6
3
3 2 5
VERTE !!!
1
5. 100 rekordów bazy danych umieszczono raz w doskonale wyważonym
drzewie binarnym, a raz w doskonale zrównoważonym drzewie rzędu 3-tego.
Jaki jest stosunek liczby poziomów obu struktur ?
6. Poniższą tablicę należy posortować tak, by w miejscu o indeksie 1 znalazł się
element najmniejszy, w miejscu o indeksie 2  drugi z kolei zgodnie z relacjÄ…
mniejszości, itd. Należy zastosować metodę  sortowania przez zliczanie
( counting sort ). Pokazać (graficznie) wszystkie fazy sortowania.
indeks 1 2 3 4 5 6 7 8 9
wartość 7 7 1 3 1 2 4 7 8
7. Dla 7-znakowego alfabetu, o częstościach względnych występowania
poszczególnych znaków podanych poniżej, wyznaczyć kody binarne Huffmana
x A B C D E F G
F(x) 10 8 12 25 1 31 11
8. Stosując algorytm potęgowania modulo wykorzystujący binarną
17
reprezentację wykładnika obliczyć 5 mod 6.. UWAGA: Pokazać wszystkie
obliczenia dokonywane w każdej  pętli algorytmu.
9. Ile różnych drzew poszukiwań binarnych można utworzyć z 4-ch węzłów o
wartościach kluczy 3, 6, 9 i 12 ? Pokazać w formie graficznej konfiguracje tych
drzew BST.
10. Ile elementów należy do grupy multiplikatywnej Z*11 ? Ile ta grupa ma
generatorów ? Czy liczba 2 jest generatorem tej grupy (odpowiedz
potwierdzić
odpowiednimi obliczeniami) ? Wyznaczyć reszty kwadratowe należące do tej
grupy multiplikatywnej.