Egzamin z Zaawansowanych algorytmów – 20.09.11
GRUPA A
Imię i nazwisko:....................................................
numer indeksu :....................................................
Za każde z zadań można otrzymać jeden punkt.
1. Dane są wzorzec P:
0 1 2 3 4 5 6 7 8
a g a c a g a c a
oraz tekst T:
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
a
g
a g
a c
a g
a
c
a
s
c
d a a a a a a
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) Z którymi znakami wzorca będzie porównany znak numer jedenaście ('s') z tekstu przez algorytm KMP zgodnie ze słabą funkcją dobrego sufiksu? (Podaj numery) Odpowiedź: …...................................
d) Z którymi znakami wzorca będzie porównany znak numer jedenaście ('s') z tekstu przez algorytm KMP zgodnie z mocną funkcją dobrego sufiksu? (Podaj numery) Odpowiedź: …...................................
2. Podaj złożoność obliczeniową następującego fragmentu kodu, przy założeniu, że f(i)=O(i) : for(i=1; i<n; i++)
{
f(i);
for(j=1; j<m; j++)
f(j);
}
Odpowiedź uzasadnij:
3. Ile może powstać cykli w grafie G, składającym się z dwóch rozłącznych drzew, po dodaniu dwóch krawędzi? (Podaj wszystkie możliwości)
Odpowiedź: ........................................
4. Dany jest graf:
0: 3 2 1
1: 0 4 2
2: 3 4 1 0
3: 2 5 0
4: 1 2
5: 3
Podaj kolejność odwiedzania krawędzi przez algorytm DFS dla tego grafu zakładając, że algorytm przegląda listy sąsiedztwa od końca.
Odpowiedź:...........................................
5, 3, 0, 1, 2, 4
5. Podaj kolejność odwiedzania krawędzi przez algorytm BFS dla tego grafu zakładając, że algorytm przegląda listy sąsiedztwa od końca.
5, 3, 2, 0, 4, 1
Odpowiedź:...........................................
6. Czy graf może zawierać więcej mostów niż punktów artykulacji?
Odpowiedź:...........................................
Uzasadnienie:...........................................
7. Jaki jest warunek konieczny i dostateczny na istnienie w grafie cyklu Eulera ?
Odpowiedź:...........................................
Dla spójnych grafów nieskierowanych warunkiem jest
parzystość stopni wszystkich wierzchołków.
Dla spójnych grafów skierowanych warunkiem jest jest taka sama liczba krawędzi wchodzących i wychodzących dla każdego wierzchołka.
Imię i nazwisko:....................................................
GRUPA A
numer indeksu :....................................................
8. Wylosowano następujące pary wierzchołków: 0-1, 2-3, 1-3, 4-5, 4-6, 7-6, 1-4.
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
0 0 1 2 7 4 5 0
9. Dany jest graf G=(V,E), E={0-1, 0-2, 0-3, 1-2, 1-5, 2-3, 2-4, 3-4, 4-5}, V={0,1,2,3,4}. Wagi odpowiednich krawędzi wynoszą: w(0-1)=6, w(0-2)=2, w(0-3)=1, w(1-2)=6, w(1-5)=5, w(2-3)=3, w(2-4)=5, w(3-4)=4, w(4-5)=5.
Podaj kolejność dodawania krawędzi do minimalnego drzewa rozpinającego przez algorytm Prima, startującego z wierzchołka 1:
Odpowiedź:..................................................
(1-5), (5-4), (4-3), (3-0), (0-2)
10. Ile maksymalnie krawędzi o minimalnej wadze może należeć do minimalnego drzewa rozpinającego spójnego grafu prostego G, o n>3 wierzchołkach i m>2n krawędziach?
Odpowiedź:..................................................
Uzasadnienie:
11. Dane są zbiór kluczy {a,b,c,d,e,f} oraz funkcja haszująca h taka, że h(d)=4, h(c)=4, h(b)=7, h(a)=5, h(e)=5, h(f)=6.
a) Uzupełnij tablicę haszującą po dodaniu kluczy a, b, c, d, e, f zgodnie z metodą liniową: 0 1 2 3 4 5 6 7
e f
c a d b
b) Z tablicy otrzymanej w poprzednim podpunkcie usuń klucz 'a', zgodnie z metodą liniową:
0 1 2 3 4 5 6 7
f
c d e b
12. Dane są wektory v1=(3,2,1), v2=(-1,1,1), v3=(1,0,0).
Oblicz (v1 x v3 | v2).
Odpowiedź:..................................................
13. Podaj jak będzie wyglądać kolejka wierzchołków, w kolejnych etapach wykonywania algorytmu Grahama, dla danych wejściowych: (0,0), (1,5), (2,4), (3,1), (5,4) Odpowiedź:..................................................
(0,0), (3,1), (5,4), (1,5)
14. Dana jest permutacja:
(1 2 3 4 5 6 7 8 9 10)
10 1 4 5 6 3 9 7 8
2
1 -> 10 -> 2 -> 1 3 -> 4 -> 5 -> 6 -> 3 7 -> 9 -> 8 -> 7
a) Z jakich cykli składa się powyższa permutacja?
Odpowiedź:..................................................
(1, 10, 2) ; (3, 4, 5, 6) ; (7, 9, 8)
b) Podaj znak powyższej permutacji:
7
Odpowiedź:..................................................
nieparzysta, bo sgn(f) = (-1) = -1
15. Jaka jest maksymalna możliwa wysokość drzewa Huffmana, dla n znaków (n>1) : Odpowiedź:..................................................
n - 1