Egzamin poprawkowy 2002/03

Zadanie 1

Słowa kluczowe: optymalne porównania

Podaj optymalny algorytm sprawdzania, czy w danym ciągu \(n\)-elementowym wszystkie elementy są takie same. Operacją dominującą jest porównanie dwóch elementów. Uzasadnij optymalność swojego rozwiązania.

Zadanie 2

Słowa kluczowe: grafy

Wierzchołkiem rozdzielającym w spójnym grafie nazywany wierzchołek, którego usunięcie rozspójnia graf. Załóżmy, że dany jest (przez listy sąsiedztwa) spójny graf \(G\) o \(n\) wierzchołkach i \(m\) krawędziach.

1. Zaproponuj prosty i efektywny algorytm, znajdujący w \(G\) wierzchołek, który nie jest wierzchołkiem rozdzielającym.

2. Ułóż efektywny algorytm, który znajdzie taką kolejność usuwania wierzchołków z grafu \(G\), że żadne usunięcie nie rozspójni aktualnego grafu.

Zadanie 3

Słowa kluczowe: struktury danych; wzbogacanie

Zaprojektuj strukturę danych dla skończonego multizbioru liczb całkowitych \(S\), umożliwiającą efektywne wykonywanie następujących operacji:

1. \(Insert(S, x, k) ::\) dodaj \(k\) egzemplarzy do zbioru \(S\).

2. \(Delete(S, x, k) ::\) usuń \(min(k, \#(x \in S))\) egzemplarzy \(x\) z \(S\).

3. \(Max(S) ::\) podaj element, który ma najwięcej wystąpień w \(S\).

Zadanie 4

Słowa kluczowe: struktury danych, amortyzacja

Na płaszczyźnie dodajemy kolejno punkty o współrzędnych \((x_i, y_i)\) i takie, że \(x_{i + 1} > x_i\). Po dodaniu kolejnego punktu łączymy go ze wszystkimi wcześniejszymi punktami i takimi, że dodana krawędź (odcinek) nie przetnie już istniejących krawędzi (jedynie wspólne punkty to końce odcinków). Definiujemy dwie funkcje:

1. \(Liczba\) - zwraca liczbę dotychczas utworzonych krawędzi,

2. \(Obwod\) - zwraca liczbę krawędzi na obwodzie figury powstałej w wyniku dodawania kolejnych punktów.

Zaprojektuj strukturę danych, która umożliwi dodawanie nowych punktów i obliczanie podanych funkcji w zamortyzowanym czasie stałym.