Ctrl+K

2. Klasówka 2019/20 (09.01.2020)

2. Klasówka 2019/20 (09.01.2020)#

Zadanie 1 [7 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie

Zaprojektuj strukturę danych, która umożliwia wydajne wykonywanie następujących operacji na dynamicznym ciągu liczbowym C:

  • init:: utwórz pusty ciąg C (operacja wykonywana tylko raz na samym początku);

  • insert(i, x):: wstaw element x jako i-ty element ciągu C (za elementem z dotychczasowej pozycji i-1 a przed dotychczasowym elementem z pozycji i), \(1 \le i \le |C|+1\);

  • delete(i):: usuń element z pozycji i z ciągu C, \(1 \le i \le |C|\);

  • Element(i):: podaj wartość elementu z pozycji i w ciągu C, \(1 \le i \le |C|\);

  • isConstant(i, j):: sprawdź, czy w podciągu C[i..j] wszystkie elementy są takie same, \(1 \le i \le j \le |C|\);

  • mostCommon:: podaj wartość najczęściej pojawiającego się elementu w ciągu C (w przypadku kilku takich elementów wystarczy podać wartość tylko jednego z nich).

Zadanie 2 [7 punktów]#

Słowa kluczowe: amortyzacja

Na początkowo pustej szachownicy o wymiarach \(N\times N\) dwaj gracze na przemian stawiają białe i czarne pionki. Gdy dwa pionki o tym samym kolorze znajdą się obok siebie (w przypadku powstania kilku takich par pionków wybieramy TYLKO JEDNĄ, dowolną z nich), zdejmujemy postawiony dopiero co pionek i zmieniamy kolor drugiego pionka w parze na przeciwny. Jeśli powstała w ten sposób co najmniej jedna nowa para sąsiednich pionków o tym samym kolorze, to postępujemy podobnie jak poprzednio - zdejmujemy dopiero co przekolorowany pionek, a jego sąsiada w parze kolorujemy na kolor przeciwny. Proces ten kontynuujemy, aż nie będzie sąsiednich pionków tego samego koloru. Podaj zamortyzowany koszt jednego posunięcia w grze, gdy postawienie pionka, zdjęcie pionka z planszy, zmiana koloru pionka są operacjami jednostkowymi.

Dokonaj analizy kosztu zamortyzowanego

  1. [3 punkty] metodą księgowania;

  2. [4 punkty] metodą funkcji potencjału.

Zadanie 3 [6 punktów]#

  1. [3 punkty] Ile jest permutacji kluczy 1,2,3,4,5,6,7, które po wstawieniu do początkowo pustego (zwykłego) drzewa BST dadzą w wyniku pełne drzewo binarne?

  2. [3 punkty] Ile jest permutacji kluczy 1,2,3,4, które po wstawieniu do początkowo pustego (zwykłego) drzewa BST dadzą w wyniku drzewo AVL?

W każdym przypadku uzasadnij poprawność zaproponowanego rozwiązania i dokonaj analizy czasowej złożoności obliczeniowej zaprojektowanych algorytmów..

Zawartość