1asdegzam6wrzesien2004

Algorytmy i Struktury Danych Wersja b

Egzamin poprawkowy, 6 wrzesień 2004, studia wieczorowe

I a). Oszacuj możliwie najlepiej rzędy wymienionych funkcji, określonych w zbiorze liczb naturalnych, używając notacji 0 i wypisz numery funkcji w porządku rosnących rzędów

fl (n) = n*lg (n³) + n² =    ............... f2(n) = n*sqrt(n) + lg nⁿ =................

f'3(n) = sin¹ (n) + 8^lgn + n =........... f4(n) = Ig (n!) + 2" + 4n =...............

kolejność po uporządkowaniu: ............................................

b)    W katalogu bibliotecznym wszystkie pozycje zostały uporządkowane alfabetycznie ze względu na nazwisko autora, a pozycje dotyczące tego samego autora, alfabetycznie ze względu na tytuł pracy. Załóżmy, że zarówno nazwiska, jak i tytuły prac sąjednowyrazowe. Jaki algorytm zapewni wykonanie najmniejszej liczby porównań przy wyszukiwaniu dowolnej pozycji w tym katalogu? Ile co najwyżej porównań słów wykona ten algorytm, jeżeli katalog zawiera nazwiska 128 autorów, a lista prac każdego z autorów zawiera co najwyżej 16 pozycji.

Jaki algorytm?.................................... Ile porównań..................................................................

c)    Ile czasu zajmie wykonanie zadania o wielkości 32 algorytmem A o złożoności n\ jeśli wiemy, że zadanie o rozmiarze 8 zajmuje (na tym samym komputerze i przy użyciu tego samego algorytmu) 64 sekundy?

2. a) Narysuj drzewo BST powstałe w wyniku kolejnego wstawienia elementów:

16. 12, 18, 0. 13, 14. 19, 17, 15 do początkowo pustego drzewa.

b) Następujący algorytm realizuje proces przekładania elementów z drzewa AVL, A. do początkowo pustego kopca H (minimum w korzeniu kopca). Zakładając, że w drzewie znajduje się n elementów, operacje min, delcie są standardowymi operacjami w strukturze drzewAVL, a insert jest operacją wstawiania elementu do kopca, oszacuj koszt tego algorytmu mierzony liczbą wykonanych porównań elementów, whilc —iempty(A) do e := min(A); H := insert(e, H); A := delete(e, A) od;

c) Jaka jest wysokość kopca otrzymanego w punkcie b) ?

3.(a) Zbuduj drzewo kodowe Huffmana. Częstotliwość występowania każdej z liter jest sumą wag krawędzi incydentnych z wierzchołkiem oznaczonym tą literą w poniższym grafie. Jeżeli dwie litery lub słowa mają tę samą częstotliwość występowania, to o porządku decyduje porządek alfabetyczny.

(b)    Zakoduj słowo „FACE”......................................................................................................

(c)    Jaka jest złożoność algorytmu budowy drzewa kodowego Huffmana dla tekstu, w którym występuje k

różnych znaków?.....................................

1

Niech X będzie zbiorem o n elementach. Oszacuj możliwie najlepiej koszt wyszukiwania elementu drugiego największego w tym zbiorze,

a.    jeśli X zapisano w tablicy.........................................

b.    jeśli X zapisano jako drzewo-kopiec .....................................................................