Egzamin z Zaawansowanych algorytmów – 24.06.11
GRUPA A
Imię i nazwisko:....................................................
numer indeksu :....................................................
Za każde z zadań można otrzymać jeden punkt. W zadaniach 2,4,5,9,10,11,15,19a za złą odpowiedź
otrzymuje się -0,5 pkt.
1. Dane są wzorzec P:
0 1 2 3 4 5 6 7 8
e d e d e d f e e
oraz tekst T:
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
e
d
e
d
e
f
e
d
e
d
c
d
a
d
a
d
a
e
e
e
e
a) Uzupełnij tabelę przesunięć dla powyższego wzorca, zgodnie ze słabą funkcją dobrego
prefiksu:
0
1
2
3
4
5
6
7
8
9
b) Uzupełnij tabelę przesunięć dla powyższego wzorca, zgodnie z mocną funkcją dobrego
prefiksu:
0
1
2
3
4
5
6
7
8
9
c) Ile razy znak numer pięć ('f') z tekstu, będzie porównywany ze znakami wzorca przez
algorytm KMP ze słabą funkcją dobrego sufiksu?
Odpowiedź: …...................................
2. Ile maksymalnie razy znak z tekstu długości n, może być porównywany ze znakami wzorca
długości m (n>2m), przez algorytm KMP w wersji słabej ?
a) n b) n-1 c) 1
d) m e) m-1
3. Graf G o n>3 wierzchołkach posiada k>2 składowych. Ile może być składowych w G po
dodaniu dwóch krawędzi (podaj wszystkie możliwości)?
Odpowiedź: ........................................
4. Jaka jest minimalna liczba krawędzi konieczna do rozspójnienia grafu pełnego o n>2
wierzchołkach?
Odpowiedź:..........................................
5. Ile maksymalnie może istnieć rozłącznych krawędziowo ścieżek pomiędzy dwoma
wierzchołkami, w drzewie o n wierzchołkach ?
a) n b) n! c) n-1 d) 1 e) 2
6. Ile istnieje różnych reprezentacji listowych podanego grafu:
0: 1 2 3
1: 0 2
2: 0 1
3: 4 0
4: 3
Odpowiedź:..........................................
7. Podaj kolejność odwiedzania wierzchołków przez algorytm DFS, dla grafu podanego w
poprzednim zadaniu, zaczynając od wierzchołka 3:
Odpowiedź:...........................................
8. Podaj kolejność odwiedzania wierzchołków przez algorytm BFS, dla grafu podanego w
zadaniu numer 6, zaczynając od wierzchołka 1:
Odpowiedź:...........................................
9. Czy graf może zawierać wyłącznie punkty artykulacji ?
Odpowiedź:...........................................
10. Jaka jest minimalna możliwa ilość punktów artykulacji w drzewie o n>3 wierzchołkach ?
Odpowiedź:...........................................
11. Czy graf może posiadać cykl Eulera i most ?
Odpowiedź:...........................................
12. Wylosowano następujące pary wierzchołków: 1-0, 2-3, 0-3, 4-5, 5-6, 5-7, 5-8, 0-5.
Wypełnij tabelkę identyfikatorów, dla algorytmu szybkiego scalania (przy konwencji
podpinania prawego poddrzewa pod lewe), dla podanych par:
0
1
2
3
4
5
6
7
8
Imię i nazwisko:....................................................
GRUPA A
numer indeksu :....................................................
13. Dany jest graf G=(V,E), E={0-1,0-3,1-3,1-2,2-3,3-4,2-4}, V={0,1,2,3,4}. Wagi
odpowiednich krawędzi wynoszą: w(3-4)=6, w(0-1)=1, w(2-4)=7, w(0-3)=2, w(1-3)=3,
w(1-2)=4, w(2-3)=5.
Podaj kolejność dodawania krawędzi do minimalnego drzewa rozpinającego przez
algorytm Kruskala:
Odpowiedź:..................................................
14. Czy jest możliwe, aby krawędź o maksymalnej wadze należała do minimalnego drzewa
rozpinającego spójnego grafu prostego G, o n>3 wierzchołkach i m>2n krawędziach, przy
założeniu, że wagi krawędzi są różne?
Odpowiedź:..................................................
Uzasadnienie:
15. Czy krawędź o minimalnej wadze musi należeć do minimalnego drzewa rozpinającego
dowolnego spójnego grafu prostego o wagach dodatnich?
Odpowiedź:..................................................
16. Dane są zbiór kluczy {a,b,c,d,e} oraz funkcja haszująca h taka, że h(d)=3, h(c)=4, h(b)=4,
h(a)=3, h(e)=1.
a) Uzupełnij tablicę haszującą po dodaniu kluczy d, c, b, a, e, zgodnie z metodą liniową:
0 1 2 3 4 5
b) Z tablicy otrzymanej w poprzednim podpunkcie usuń klucz 'd', zgodnie z metodą
liniową:
0 1 2 3 4 5
17. Dane są wektory v1=(1,0,0,0), v2=(0,3,2,1), v3=(1,-1,1,1), v4=(1,1,0,0). Podaj wszystkie
pary wektorów ortogonalnych:
Odpowiedź:..................................................
18. Jaka jest minimalna możliwa ilość krawędzi, tworzących otoczkę wypukłą zbioru,
będącego sumą zbiorów wierzchołków dwóch wielokątów wypukłych o k i n
bokach (k>3, n>3)?
Odpowiedź:..................................................
19. Dana jest permutacja:
a) Jaki jest znak powyższej permutacji?
Odpowiedź:..................................................
b) Podaj permutację odwrotną do powyższej:
20. Plik zawiera tekst „abababcababcabda”.
a) Podaj drzewo Huffmana dla tego pliku:
b) Podaj zakodowany tekst (w postaci zer i jedynek):
(
1
2 3 4 5 6 7 8 9 10
10 2 4 5 6 3 9 7 8
1
)