ASD e 02 2005 2

Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko

Nr studenta............Nr grupy

Zadanie 2(10punktów) Do serwera spływają dane z różnych krajów. Są one tymczasowo przechowywane w blokach o długości 10000 elementów. Uwaga: mamy dowolną liczbę bloków, ale do każdego kraju w danej chwili przyporządkowany jest tylko jeden blok. Pojedynczym elementem bloku jest tekst złożony z 8 dużych liter alfabetu angielskiego. Gdy jakiś blok zostanie całkowicie zapełniony, wówczas wszystkie elementy z tego bloku są zapamiętywane na serwerze, a następnie są one usuwane z tego bloku i może być on ponownie wykorzystany. Operacjami jakie można, wykonać na bloku B są:

B.get(i) - zwraca i-ty element z bloku B,

B.set(e,i) - wstawia element e na i-tą pozycję w bloku B.

Polecenia:

1.    Zaproponuj (ew. narysuj) taką strukturę, aby czas zapamiętywania bloków danych na serwerze oraz czas wyszukiwania danych był minimalny.

2.    Podaj szkic algorytmu zapamiętywania bloków danych na serwerze.

3.    Podaj szkic algorytmu wyszukiwania danych. Parametrami algorytmu wyszukiwania powinny być: poszukiwana dana (tzn. ciąg znakowy) oraz kraj, z którego pochodzi.

4.    Ustal złożoność każdego z podanych algorytmów.

Nie zapomnij precyzyjnie określić co stanowi argument funkcji złożoności.