Egzamin poprawkowy 2001/02

Zadanie 1

Słowa kluczowe: sortowanie

1. Zaproponuj efektywny algorytm sortowania przez porównania ciągów \(n\)-elementowych, o których wiadomo, że zawierają co najwyżej \(1 \leq m \leq n\) różnych wartości.

2. Zaproponuj algorytm sortowania niemalejąco i w miejscu ciągu dwuwartościowego \(a[1..n]\) za pomocą minimalnej liczby porównań \(=\) lub \(<\). Uzasadnij poprawność swojego rozwiązania.

Zadanie 2

Słowa kluczowe: struktury danych; wzbogacanie

Dany jest \(n\)-kąt wypukły \(W\), którego wierzchołki są ponumerowane kolejno \(1, 2, \cdots, n\). Zaproponuj strukturę danych, która umożliwia efektywne wykonywanie następujących operacji:

1. \(Add(j) ::\) dodaje do wielokąta \(W\) przekątną \(1\) - \(j\), \(2 < j < n\), jeśli nie ma jej już w wielokącie \(W\).

2. \(Remove(j) ::\) usuń z \(W\) przekątną \(1\)-\(j\), \(2 < j \leq j < n\).

3. \(Max() ::\) zwraca największą możliwą liczbę boków ograniczających pewien obszar nie zawierający w swoim wnętrzu przekątnych.

Zadanie 3

Słowa kluczowe: grafy

Dany jest spójny graf \(G = (V, E)\), którego wierzchołki pomalowane są pięcioma kolorami. Znajdź dla każdego koloru minimalną odległość pomiędzy różnymi wierzchołkami tego samego koloru.