ASD ep 02 2005 1

Algorytmy i Struktury Danych

Egzamin poprawkowy 16 lutego 2005

Imię i nazwisko

...........................................Nr indeksu

1    2    3    4    5 suma

Zadanie 1 Zbiór słów pewnego słownika jest przechowywany w drzewie AVL, utworzonym zgodnie z porządkiem leksykograficznym. Ponadto, dana jest operacja porównaj (w,w’), która dla dowolnych dwóch słów w i w’ zwraca 0, gdy słowa są identyczne, zwraca 1, gdy w jest wcześniej w porządku leksykograficznym niż w’,

, a w przeciwnym przypadku zwraca-1.    ;

Polecenia:    ,

(a)    Mając dany korzeń drzewa-słownika zaproponuj procedurę wypisującą wszystkie słowa, które występują w tym słowniku pomiędzy dwoma zadanymi słowami w, w’ (podanymi jako parametry), według porządku leksykograficznego.

(b)    Oszacuj złożoność czasową podanego algorytmu.