Ctrl+K

Egzamin 1997/98

Egzamin 1997/98#

Zadanie 1#

Słowa kluczowe: struktury danych; wzbogacanie

Zaprojektuj strukturę danych umożliwiającą wykonanie poniższych operacji na dynamicznym, skończonym podzbiorze \(S\) zbioru punktów okręgu o środku w środku układu współrzędnych i promieniu jednostkowym:

  1. \(Dodaj(S, (x, y))\):: dodaj punkt o współrzędnych \((x, y)\) do zbioru \(S\);

  2. \(Usun(S, (x, y))\):: usuń punkt o współrzędnych \((x, y)\) ze zbioru \(S\);

  3. \(NajOdl(S, (x, y))\):: jeśli \(S \neq \emptyset `, to dla danego punktu :math:`(x, y)\) na okręgu znajdź w \(S\) punkt najbardziej odległy od punktu \((x, y)\);

  4. \(IlePunktow(S, (x', y'), (x'', y''))\):: zwróć liczbę punktów na łuku domkniętym o początku w \((x', y')\) i końcu w \((x'', y'')\) w kierunku przeciwnym do ruchu wskazówek zegara.

Opis strukturę danych i sposób implementacji każdej z powyższych operacji. Przeanalizuj złożoność zaproponowanych algorytmów.

Zadanie 2#

Słowa kluczowe: struktury danych, amortyzacja

Załóżmy, że chcemy wykonywać operacje \(Search\) i \(Insert\) na zbiorze \(n\)-elementowym. Niech \(k = \lfloor \log (n + 1) \rfloor\) i niech \(<n_{k-1}, n_{k-2}, \cdots, n_0>\) będzie binarną reprezentacją \(n\). Mamy \(k\) tablic \(A_0, A_1, \cdots, A_{k-1}\). Tablica \(A_i\) ma rozmiar \(2^i\). Każda tablica \(A_i, i = 0, 1, \cdots, k - 1\), jest albo pusta, albo w całości zapełniona w zależności od tego, czy \(n_i = 0\), czy \(n_i = 1\). Zapełnione tablice są uporządkowane rosnąco. Nie ma żadnych szczególnych zależności pomiędzy elementami z różnych tablic.

  1. Opisz sposób wykonywania operacji \(Search\) na tej strukturze danych. Oszacuj pesymistyczny czas działania tej operacji.

  2. Opisz sposób wstawiania nowego elementu do tej struktury. Przeanalizuj jego pesymistyczny i zamortyzowany czas działania.

Zadanie 3#

Słowa kluczowe: sortowanie; scalanie

Zaprojektuj efektywny algorytm, który scala \(k\) uporządkowanych ciągów liczb całkowitych \(A_1, A_2, \cdots, A_k\) o sumarycznej długości \(n\) w jeden ciąg uporządkowany.

  1. Przy założeniu, że różnica między kolejnymi elementami każdego ciągu wynosi co najwyżej 10.

  2. Bez żadnych dodatkowych założeń o elementach scalanych ciągów.

Przeanalizuj złożoność każdego algorytmu jako funkcję \(k\) i \(n\).

Zadanie 4#

Z szachownicy \(n \times n\) wycięto \(k\) pól, \(0 \leq k \leq n^2\). Zaprojektuj algorytm, który w czasie \(O(n^3)\) sprawdzi, czy można szachownicę pokryć kostkami domina.

Zawartość