2. Klasówka 2022/23 (12.01.2023)#

Zadanie 1 [2 punkty]#

Słowa kluczowe: struktury danych, AVL

Podaj największe takie d, że każde AVL-drzewo o wysokości \(h = 2023\) do głębokości d jest pełnym drzewem binarnym. Uwaga: głębokości i wysokości drzew liczymy w liczbach krawędzi.

Podpowiedź

  • \(h=1\) odpowiedzią jest 0,

  • \(h=3\) odpowiedzią jest 1,

  • \(h=2k+1\) odpowiedzią jest k,

Drzewo o najmniejszej pełnej głębokości jest skrajnie przechylone w jedną stronę, np.

  • T(1) to korzeń tylko z jednym liściem (lewym synem)

  • T(h) to drzewo w którym lewe poddrzewo korzenia to T(h-1) a prawe poddrzewo to T(h-2)

Zadanie 2 [6 punktów]#

Słowa kluczowe: struktury danych; wzbogacanie

Zaprojektuj strukturę danych, która na początkowo pustym, dynamicznym zbiorze S dodatnich liczb całkowitych, pozwala wydajnie wykonywać następujące operacje:

  • INI():: \(S := \emptyset\) (wykonywana tylko raz, na samym początku)

  • INSERT(n):: \(S := S \cup \{n\}\)

  • DELETE(n):: \(S := S - \{n\}\)

  • SEARCH(n):: sprawdź, czy n jest w zbiorze S

  • MAX():: jeśli S jest niepusty, to podaj największą liczbę w zbiorze S

  • INCREASE(i):: jeśli S jest niepusty dodaj MAX() do i najmniejszych elementów w zbiorze, \(1 \le i \le |S|\)

Podpowiedź

Wzbogacamy drzewo zrównoważone o dodatkowe atrybuty:

  • size: rozmiar podrzewa

  • max: maksymalna wartość w poddrzewie

  • add: wartość którą należy dodać do wszystkich elementów w poddrzewie

Po uwzględniu wartości klucza i atrybutów add na ścieżce od węzła do korzenia, drzewo zachowuje własności BST. Aby uprościć operacje INSERT/DELETE, za każdym razem gdy przechodzimy po wężle w którym add jest różna od 0, stosujemy ją do klucza i przepychamy do poddrzew. Operację INCREASE możemy zaimplementować przez kombinację operacj SPLIT, aktualizacji add w korzeniu i JOIN.

Zadanie 3 [12 punktów]#

Słowa kluczowe: grafy; dwuspójność

Grafem klikowym nazywamy spójny, nieskierowany graf, w którym każda dwuspójna wierzchołkowo składowa jest kliką (grafem pełnym).

  1. [2 punkty] Jaka jest maksymalna, a jaka minimalna wysokość DFS-drzewa w 2023- wierzchołkowym grafie klikowym, zawierającego dokładnie 3 dwuspójne składowe.

  2. [10 punktów] Dla liczby całkowitej \(n > 1\) i liczby całkowitej k, \(1 \le k < n\), rozważmy n-wierzchołkowy graf klikowy G o zbiorze wierzchołków \(\{1, 2, \ldots, n\}\), w którym dwuspójne składowe ponumerowano \(1, 2, \ldots, k\). Zwartą reprezentacją grafu G, oznaczaną przez Z(G), nazywamy zbiór wszystkich par \((v,s_v)\) takich, że v jest wierzchołkiem grafu, natomiast \(s_v\) jest numerem dwuspójnej składowej, do której należy wierzchołek v.

    1. [2 punkty] Jaki jest rozmiar zbioru Z(G)?

    2. [2 punkty] Uzasadnij, że wysokość DFS-drzewa budowanego algorytmem rekurencyjnym na grafie zadanym przez listy sąsiedztwa zależy od kolejności wierzchołków na listach.

    3. [6 punktów] Dana jest zwarta reprezentacja Z(G) grafu G. Zaproponuj wydajny algorytm, który wyznaczy DFS-numerację wierzchołków grafu (numerujemy wierzchołki w kolejności pierwszych odwiedzin) przy przeszukiwaniu od wierzchołka o numerze 1 i przy założeniu, że listy sąsiedztwa grafu G byłyby uporządkowane rosnąco.

Podpowiedź

TBD

Uwaga: uzasadnij poprawność swoich odpowiedzi i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.