2. Klasówka 2002/03#

Zadanie 1 [8 punktów]#

Słowa kluczowe: struktury danych; wzbogacanie

Zaprojektuj strukturę danych umożliwiającą wykonywanie na skończonym zbiorze liczb rzeczywistych \(X\) następujących operacji:

  1. \(Empty(X) ::\) \(X := \emptyset\)

  2. \(Insert(X, x) ::\) \(X := X \cup \{x\}\)

  3. \(Delete(X, x) ::\) \(X := X \setminus \{x\}\)

  4. \(Closest(X) ::\) return \(\min_{x, y \in X,\ x \neq y} |x - y|\)

Opisz algorytm wykonywania poszczególnych operacji i zanalizuj ich złożoność.

Zadanie 2 [7 punktów]#

Słowa kluczowe: grafy; DFS

Dany jest spójny, nieskierowany graf \(G = (V, E)\) i zbiór krawędzi \(F\subseteq E\) pewnego drzewa rozpinającego. Zaproponuj efektywny algorytm, który sprawdza, czy można tak zbudować listy sąsiedztwa dla grafu \(G\), żeby krawędzie z \(F\) były krawędziami DFS-drzewa rozpinającego \(G\) o korzeniu w wierzchołku \(1\). (Uwaga: zakładamy, że \(V = \{ 1, 2, \cdots, n \}\) i że graf \(G\) jest dany przez listy sąsiedztwa.) Uzasadnij poprawność i przeanalizuj złożoność swojego rozwiązania.

Zadanie 3 [5 punktów]#

Słowa kluczowe: grafy; kaktusy, grafy; MST

Kaktusem nazywamy graf spójny, w którym każda dwuspójna składowa jest cyklem elementarnym. Rozważamy kaktusy z wagami na krawędziach. Zaproponuj efektywny algorytm obliczania minimalnego drzewa rozpinającego w kaktusie z wagami. Uzasadnij poprawność i przeanalizuj złożoność swojego rozwiązania.