Egzamin poprawkowy 2014/15 (luty 2015)#

Zadanie 1 (21 punktów)#

Słowa kluczowe: sortowanie, struktury danych, BST

W tym zadaniu rozważamy liczbowe ciągi różnowartościowe o długości n > 0. Niech T będzie n wierzchołkowym drzewem binarnym. Powiemy, że ciąg \(\alpha = \langle a_1, a_2,\ldots,a_n \rangle\) jest zgodny z T, jeśli po wykonaniu ciągu operacji Wstaw(\(a_1\)), Wstaw (\(a_2\)),…, Wstaw (\(a_n\)), do początkowo pustego drzewa wyszukiwań binarnych, otrzymamy drzewo izomorficzne z T.

Przykład

Permutacja \(\langle 4, 6, 5, 2, 3, 1, 7 \rangle\) jest zgodna z pełnym drzewem binarnym o wysokości 2.

  1. (4 punktów) Dana jest dodatnia liczba całkowita \(n \ge 3\) oraz ciąg \(\alpha = <a_1, a_2,\ldots,a_n>\), zgodny z pewnym drzewem binarnym o wysokości n-2. Zaprojektuj algorytm, który w czasie liniowym posortuje ciąg \(\alpha\).

  2. (4 punktów) Udowodnij, że sortowanie przez porównania ciągu zgodnego z pełnym drzewem binarnym wymaga w pesymistycznym przypadku \(\Omega(n \log n)\) porównań.

  3. (4 punktów) Zaproponuj algorytm, który w n-elementowym ciągu \(\alpha\), \(n \ge 3\), zgodnym z pełnym drzewem binarnym, znajduje element maksymalny w mniej niż n-1 porównań.

  4. [2 punkty] Rozwiąż (asymptotycznie) równanie rekurencyjne:

    \(T[1] = 0\)

    \(T[n] = T[n\ \textrm{div}\ 2] + n\).

  5. (7 punktów) Zaproponuj algorytm, który w czasie liniowym sprawdzi, czy dana permutacja \(\alpha\) liczb naturalnych 1, 2, … , n jest zgodna z pełnym drzewem binarnym.

Uwaga: przez pełne drzewo binarne rozumiemy drzewo w którym wszystkie poziomy są w pełni zapełnione wierzchołkami, od poziomu 0 do poziomu h, gdzie h to wysokość drzewa.

Zadanie 2 (10 punktów)#

Słowa kluczowe: grafy

Niech G=(V,E) będzie n-wierzchołkowym grafem spójnym, zadanym przez listy sąsiedztwa. Z każdą krawędzią grafu G jest związana dodatnia, całkowitoliczbowa waga.

  1. [4 punkty] Przy założeniu, że graf G zawiera co najwyżej n+4 krawędzie zaproponuj efektywny algorytm obliczający jego minimalne drzewo rozpinające.

  2. [2 punkty] Uzasadnij, że liczba wierzchołków w G o nieparzystych stopniach jest parzysta.

  3. [4 punkty] Zaproponuj efektywny algorytm, który połączy wierzchołki o nieparzystym stopniu w G w pary i wyznaczy zbiór parami krawędziowo rozłącznych ścieżek łączących wierzchołki w parach.

Zadanie 3 (9 punktów)#

Słowa kluczowe: teksty

W tym zadaniu rozważamy skończone słowa nad alfabetem {a,b,c}. Dla słowa długości n i liczby k, \(0 \le k \le n\), zaproponuj efektywne algorytmy obliczania:

  1. [3 punkty] liczby wszystkich podsłów zawierających dokładnie k wystąpień litery a;

  2. [6 punktów] liczby wszystkich różnych podsłów (różniących się długościami lub co najmniej jedną literą) zawierających dokładnie k wystąpień litery a.

Uwaga: w każdym zadaniu wykaż poprawność swojego rozwiązania i dokonaj analizy złożoności obliczeniowej zaproponowanego algorytmu.