Egzamin poprawkowy 2009/10

Zadanie 1

Słowa kluczowe: struktury danych, wzbogacanie

Dane są, dodatnia liczba całkowita \(n\) oraz tablica liczb całkowitych \(a[1..n]\). Dla każdego podzbioru \(S\) zbioru indeksów \(\{1,2, \cdots, n\}\) wagą \(w(S)\) nazywamy sumę elementów tablicy \(a\) o indeksach z tego zbioru. Przyjmujemy, ze wagą zbioru pustego jest \(0\). Zbiór indeksów nazwiemy niezależnym, jeśli nie zawiera dwóch kolejnych indeksów.

1. Zaproponuj algorytm, który obliczy wagę najcięższego zbioru niezależnego \(S\).

2. Na tablicy \(a\) wykonujemy operacje:

   1. \(NewVal(i,x) :: a[i] := x\); \(1 \leq i \leq n\), \(x\) - liczba całkowita,

   2. \(MaxWeight ::\) podaje wagę najcięższego zbioru niezależnego \(S\).

   Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie operacji \(NewVal\) i \(MaxWeight\).

Zadanie 2

Słowa kluczowe: struktury danych, kolejka dwumianowa

Dana jest \(n\)-węzłowa kolejka dwumianowa \(Q\) oraz \(k\) nowych kluczy. Zaproponuj algorytm, który w czasie \(O(k + \log n)\) rozszerzy \(Q\) o nowe klucze.

Zadanie 3

Słowa kluczowe: teksty

Zaproponuj algorytm, który dla danego tekstu \(T\) i dodatniej liczby całkowitej \(k\) wyznaczy liczbę niepustych podsłów pojawiający się w \(T\) co najmniej \(k\) razy.

Zadanie 4

Słowa kluczowe: grafy, DFS

Niech \(n\) będzie dodatnią liczbą całkowitą. Drabiną rzędu \(n\) nazywamy graf o wierzchołkach \(1, 2, \cdots, 2n\) i krawędziach łączących wierzchołki \(2k - 1\) z \(2k\), dla \(k = 1, 2, \cdots, n\) oraz \(2k - 1\) z \(2k + 1\) i \(2k\) z \(2(k+1)\), dla \(k = 1, 2, \cdots, n - 1\). Ile różnych drzew DFS o korzeniu w wierzchołku \(1\) można zbudować dla drabiny rzędu \(n\).