ASD e 02 2006 1

WERSJA

ALGORYTMY I STRUKTURY DANYCH

studia dzienne, egzamin 3 luty 2006

vstkie odpowiedzi muszą być uzasadnione. Odpowiedzi bez uzasadnienia będą

oceniane na 0 punktów. Powodzenia.

Imię i nazwisko.....

nr indeksu.....................nr grupy

Zadanie 1. (441+243)

Niech będzie dany tekst    r»>/nwh znaków. Częstości występowania tych

znaków w tekście T dane są w poniższej tabelce

znak	a	h	c	d
częstość występowania	95	70	60	50

(a)    Zbuduj drzewo kodowe prefiksowego kodu HulYmana dla tekstu I X I Przedstaw kolejne etapy budowy drzewa

(b)    Jaka pomocnicza struktura danych jest używana w tym algorytmie i do czego?

(c)    Przedstaw opis metody odkodowywania zakodowanego tekstu T, jeśli dany jest korzeń r drzewa kodowego HufTmana, które posłużyło do zakodowania tekstu TXT, i oszacuj jej koszt.

(d)    Przedstaw pseudokod zaproponowanego w punkcie (c) algorytmu