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

)