2. Klasówka 2012/13#
Zadanie 1#
Zaprojektuj strukturę danych, która umożliwia efektywne wykonywanie ciągu operacji Łącz\((u,v)\) i Głębokość\((u)\) na lesie drzew ukorzenionych o zbiorze wierzchołków \(\{1, 2, \cdots, n\}\). Początkowo każde drzewo jest jednowierzchołkowe. Operacja Łącz\((u,v)\) polega na połączeniu dwóch różnych drzew o korzeniach \(u\) i \(v\) w jedno drzewo o korzeniu \(v\), poprzez uczynienie \(u\) synem \(v\) (podwiązanie \(u\) do \(v\)). Operacja Głębokość\((u)\) polega na wyznaczeniu głębokości wierzchołka \(u\) w aktualnie zawierającym go drzewie w lesie. Podaj sposób i koszt inicjacji swojej struktury danych, a następnie koszt wykonania każdej z operacji Łącz i Głębokość w zaprojektowanym przez siebie rozwiązaniu.
Przykład: Dla \(n = 5\), po wykonaniu operacji Łącz\((1,2)\), Łącz\((2,3)\), Łącz\((3,4)\), Łącz\((4,5)\) wynikiem Głębokość\((2)\) jest \(3\).
Zadanie 2#
Zaprojektuj strukturę danych, która pamięta dynamiczny ciąg liczbowy \(x_1, x_2, \cdots, x_n\) i pozwala na wydajne wykonywanie następujących operacji:
Ini\(()\): zainicjuj ciąg jako pusty;
Usuń\((i)\) : usuń \(i\)-ty element ciągu;
Wstaw\((i,a)\): wstaw liczbę \(a\) jako \(i\)-ty element ciągu;
Podaj\((i)\): podaj \(i\)-ty element ciągu;
Suma_parzystych\(()\): podaj sumę wszystkich elementów na pozycjach parzystych w ciągu.
Zadanie 3#
Do początkowo pustej (zwykłej) kolejki dwumianowej wstawiono kolejno \(23\) elementy:
\(5, 8, 3, 20, 1, 19, 6, 9, 22, 17, 21, 20, 4, 2, 7, 11, 12, 10, 14, 13, 16, 18, 23\)
Ile drzew dwumianowych zawiera ta kolejka?
Podaj elementy, które znajdują się w korzeniach drzew dwumianowych w tej kolejce.
Ile jest liści we wszystkich drzewach w tej kolejce?