1071146164372690387641™2704897 n

Egzamin z Zaawansowanych algorytmów - 24.06.14

GRUPA A

ImiÄ™ i nazwisko:, numer indeksu

8. (2 pkl.) Do czego potrzebny jest algorytm union-fnul w algorytmie Kruskala? Odpowiedź:

9. (4 pkl) Dany jest grafG=(V,E), F.= {0-l, 0-2, 0-4. 1-2. 1-3. 2-4, 3-4. 4-5). V={ 0.1,2,3,4.5}. Wagi odpowiednich krawÄ™dzi wynoszÄ…: w(0-l)=5. w(0-2)=l. w(0-4)=5, w(l-2)=3. w(l-3)=8. w(2-4)=2, w(3-4)=4, w(4-S)=2.

a)    Podaj kolejność dodawania krawÄ™dzi do minimalnego drzewa rozpinajÄ…cego przez algorytm Prima, startujÄ…cego z wierzchoÅ‚ka 0:

Odpowiedź:..................................................

b)    Podaj kolejność dodawania krawÄ™dzi do minimalnego drzewa rozpinajÄ…cego przez algorytm Kruskala

Odpowiedź:...,..............................................

1 o. (2 pkt.) Jak zmodyfikować algorytm Kruskala tak. aby znajdował maksymalne drzewo rozpinające.

Odpowiedź:

11 (₂ pkt) Dane sÄ… zbiór kluczy {a.b.c.d.c.f} oraz funkcja haszujÄ…ca h takia. że h(a) 3. h(b)=5, h(c)=7. h(d)=5. h(e)=6, h(f)=2.

Uzupełnij tablicę haszująeą po dodaniu kluczy a. b. c, d. e, f (w tej kolejności) zgodnie / metodą liniową:

OI2 3 4 5 6 7