ASD ep 08 2003 C 1

Algorytmy i Struktury Danych (grupa C)

Egzamin poprawkowy PJWSTK 8 września 2003

Zadanie 1

(a)    Pod każdą z wymienionych funkcji zmiennej naturalnej n, n>0, napisz jej oszacowanie (w możliwie najprostszej postaci) przy pomocy notacji 0 :

f, (n) = Vn + Ig n!    f₂(n) = n ⁰⁵+(lg n)² f₃ (n) = n lg(n²) + n lg(n³)    £*(n) = 3'*" + n⁵

(b)    Uporządkuj wyżej wymienione funkcje w porządku rosnących rzędów, wypisując tylko ich numery:

(c) Niech f będzie funkcją określoną w zbiorze liczb naturalnych większych od zera, f(n) = (n^: + 3n+100)/(n²+l). Oceń. czy podane ograniczenia funkcji są, czy nic są poprawne:

ffnlsOfn^5)	tak	nic
f(n) = 0(n)	tak	nic
f(n) = n(lg n)	tak	nie

Zadanie 2

Niech M będzie macierzą sąsiedztwa (incydcncji) pewnego krawędź niezorientowanego grafu G. którego wierzchołki zostały ponumerowane od 1 do 5. Element M(i,j) macierzy M określa wagę krawędzi od wierzchołka i do wierzchołka j. Waga 0 oznacza, że odpowiadająca krawędź nie istnieje.

0	3	0	5	1
3	0	1	3	0
0	1	0	2	1
5	3	2	0	3
1	0	1	3	0

M:    ______________    Graf:    Drzewo najkrótszych ścieżek:

(a)    Narysuj ten graf oraz drzewo najkrótszych ścieżek (od wierzchołka 1 do wszystkich innych wierzchołków tego grafu) otrzymane w wyniku działania algorytmu Dijkstry.

(b)    Podaj kolejność, w jakiej są akceptowane krawędzie tego drzewa.......................................................................

(c)    Czy dla jednego grafu można zbudować dwa różne drzewa najkrótszych ścieżek? (Odpowiedź uzasadnij)

Zadanie 3

Rozważmy macierz sąsiedztwa (incydcncji) M z poprzedniego zadania, (a) Zbuduj drzewo prefiksowego kodu Huffmana dla wag w macierzy M:

(b) Korzystając ze znalezionego w punkcie (a) kodu Huffmana zakoduj pierwszy wiersz macierz M.