3asdegzam6wrzesien2004

K.(a) Narysuj dowolne drzewo rozpinające podanego niżej grafu i oblicz jego koszt Koszt:................

(b)    Ile wynosi suma wag krawędzi w minimalnym drzewie rozpinającym niezorientowanego i spójnego grafu o

200 wierzchołkach i 215 krawędziach, jeżeli waga każdej krawędzi wynosi 7?.....................................

(c)    Znajdź minimalne drzewo rozpinające grafu algorytmem Kruskala. Przedstaw kolejne etapy wykonania algorytmu.

9. Zaproponuj algorytm znajdowania przecięcia t.m. dwóch zbiorów liczbowych zapisanych w tablicach A i B, jeśli wiadomo, że elementami zbiorów są liczby naturalne trzycyfrowe.

d.    Opisz słowami metodę .

e.    Napisz pseudokod algorytmu.

f.    Oszacuj koszt.

10. Dane są dwa zbiory liczbowe X i Y. W zbiorze X wyszukujemy element największy nwX, a w zbiorze Y wyszukujemy element najmniejszy nmY. Jeśli nwX > nmY to zamieniamy te elementy, tak by nwX znalazło się w zbiorze Y, a nmY w zbiorze X. Powtarzamy to postępowanie dopóki nierówność nwX > nmY jest spełniona.

c.    Co robi ten algorytm?

f.    Jakiej struktury danych powinniśmy użyć aby zminimalizować koszt algorytmu?

g.    Napisz pseudokod algorytmu, zakładając, że wszystkie operacje wybranej przez Ciebie struktury danych zostały wcześniej zaimplementowane.

h.    Oszacuj koszt podanego algorytmu.