|
Domanda |
Risposta |
Czym jest drzewo ukorzenione (rooted tree)? inizia ad imparare
|
|
Jest to drzewo puste lub węzeł (korzeń) zawierający listę poddrzew.
|
|
|
W terminologii drzew, co to jest 'syn' (child) węzła n1? inizia ad imparare
|
|
Jest to korzeń jednego z poddrzew węzła n1.
|
|
|
Węzeł o stopniu 0 w drzewie nazywany jest _____. inizia ad imparare
|
|
|
|
|
Jaka jest definicja 'głębokości' (depth) węzła w drzewie? inizia ad imparare
|
|
Jest to długość ścieżki od korzenia do tego węzła.
|
|
|
Czym jest 'wysokość' (height) drzewa? inizia ad imparare
|
|
Jest to maksymalna głębokość dowolnego węzła w drzewie.
|
|
|
Co odróżnia drzewo uporządkowane od nieuporządkowanego? inizia ad imparare
|
|
W drzewie uporządkowanym synowie każdego węzła wewnętrznego są liniowo uporządkowani.
|
|
|
Zdefiniuj drzewo binarne. inizia ad imparare
|
|
Jest to drzewo puste lub węzeł składający się z co najwyżej dwóch poddrzew binarnych (lewego i prawego).
|
|
|
W jakiej kolejności odwiedzane są węzły w przechodzeniu drzewa metodą PREORDER? inizia ad imparare
|
|
Najpierw korzeń, potem lewe poddrzewo, a na końcu prawe poddrzewo.
|
|
|
W jakiej kolejności odwiedzane są węzły w przechodzeniu drzewa metodą INORDER? inizia ad imparare
|
|
Najpierw lewe poddrzewo, potem korzeń, a na końcu prawe poddrzewo.
|
|
|
W jakiej kolejności odwiedzane są węzły w przechodzeniu drzewa metodą POSTORDER? inizia ad imparare
|
|
Najpierw lewe poddrzewo, potem prawe poddrzewo, a na końcu korzeń.
|
|
|
Jaka jest minimalna wysokość 'h' drzewa binarnego o 'n' węzłach? inizia ad imparare
|
|
Minimalna wysokość wynosi $h \approx \log_2 n$ dla drzewa zrównoważonego.
|
|
|
W tablicowej implementacji drzewa binarnego, jaki jest wzór na pozycję lewego syna węzła o indeksie 'n' (przy indeksowaniu od 0)? inizia ad imparare
|
|
Pozycja lewego syna to $2 * n + 1$.
|
|
|
W tablicowej implementacji drzewa binarnego, jaki jest wzór na pozycję prawego syna węzła o indeksie 'n' (przy indeksowaniu od 0)? inizia ad imparare
|
|
Pozycja prawego syna to $2 * n + 2$.
|
|
|
Jaka jest złożoność czasowa operacji SIZE i HEIGHT dla wskaźnikowej implementacji drzewa binarnego? inizia ad imparare
|
|
Złożoność czasowa obu operacji wynosi $O(n)$.
|
|
|
Zdefiniuj Binarne Drzewo Poszukiwań (BST). inizia ad imparare
|
|
Jest to drzewo binarne, w którym wartości w lewym poddrzewie węzła są mniejsze od wartości węzła, a wartości w prawym poddrzewie są od niej większe.
|
|
|
Jaka jest złożoność czasowa operacji SEARCH w drzewie BST w najgorszym przypadku? inizia ad imparare
|
|
W najgorszym przypadku (drzewo zdegenerowane) złożoność wynosi $O(n)$.
|
|
|
Jak w drzewie BST znaleźć węzeł o minimalnej wartości? inizia ad imparare
|
|
Należy przemieszczać się od korzenia w lewo tak długo, jak to możliwe.
|
|
|
Co to jest 'następnik' (successor) węzła 'n' w drzewie BST? inizia ad imparare
|
|
Jest to węzeł o najmniejszej wartości spośród wszystkich wartości większych od wartości węzła 'n'.
|
|
|
Jak znaleźć następnika węzła 'n' w drzewie BST, jeśli 'n' posiada prawe poddrzewo? inizia ad imparare
|
|
Następnikiem jest węzeł o minimalnej wartości w prawym poddrzewie węzła 'n'.
|
|
|
Opisz trzeci przypadek usuwania węzła 'n' z drzewa BST (gdy 'n' ma obu synów). inizia ad imparare
|
|
Należy znaleźć następnika (lub poprzednika) 's' węzła 'n', skopiować dane z 's' do 'n', a następnie usunąć węzeł 's'.
|
|
|
|
inizia ad imparare
|
|
Jest to binarne drzewo poszukiwań, w którym dla każdego węzła wysokość jego lewego i prawego poddrzewa różni się co najwyżej o 1.
|
|
|
Jak definiuje się współczynnik zrównoważenia (balance factor, bf) węzła 'n' w drzewie AVL? inizia ad imparare
|
|
Jest to różnica wysokości lewego i prawego poddrzewa: $bf(n) = h_L(n) – h_P(n)$.
|
|
|
Jakie wartości może przyjmować współczynnik zrównoważenia (bf) dla dowolnego węzła w drzewie AVL? inizia ad imparare
|
|
Współczynnik zrównoważenia (bf) może przyjmować wartości z zestawu $\{-1, 0, 1\}$.
|
|
|
W jakim celu w drzewach AVL stosuje się rotacje? inizia ad imparare
|
|
Rotacje są mechanizmem przywracającym własność drzewa AVL (równowagę) po operacjach wstawiania lub usuwania węzłów.
|
|
|
Kiedy wykonywana jest rotacja pojedyncza RR w drzewie AVL? inizia ad imparare
|
|
Gdy prawe poddrzewo węzła jest wyższe od lewego o więcej niż 1, a problem jest spowodowany wstawieniem do prawego poddrzewa prawego syna.
|
|
|
Kiedy wykonywana jest rotacja pojedyncza LL w drzewie AVL? inizia ad imparare
|
|
Gdy lewe poddrzewo węzła jest wyższe od prawego o więcej niż 1, a problem jest spowodowany wstawieniem do lewego poddrzewa lewego syna.
|
|
|
Z jakich rotacji prostszych składa się rotacja podwójna RL? inizia ad imparare
|
|
Rotacja RL jest złożeniem rotacji LL (dla węzłów B i C) oraz rotacji RR (dla węzłów A i C).
|
|
|
Z jakich rotacji prostszych składa się rotacja podwójna LR? inizia ad imparare
|
|
Rotacja LR jest złożeniem rotacji RR (dla węzłów B i C) oraz rotacji LL (dla węzłów A i C).
|
|
|
Jaka jest złożoność czasowa operacji INSERT, DELETE i SEARCH w drzewie AVL? inizia ad imparare
|
|
Złożoność czasowa tych operacji wynosi $O(\log_2 n)$.
|
|
|
Czym jest 'lista' jako abstrakcyjny typ danych (ADT)? inizia ad imparare
|
|
Jest to ciąg 0 lub większej liczby elementów danego typu, uporządkowanych liniowo zgodnie z ich pozycją.
|
|
|
Jaką złożoność czasową ma operacja wstawienia elementu na początek listy (PREPEND) w implementacji tablicowej? inizia ad imparare
|
|
Operacja PREPEND w implementacji tablicowej ma złożoność $O(n)$, ponieważ wymaga przesunięcia wszystkich istniejących elementów.
|
|
|
Jaką złożoność czasową ma operacja wstawienia elementu na początek listy (PREPEND) w implementacji opartej na liście pojedynczo wiązanej? inizia ad imparare
|
|
Operacja PREPEND w implementacji listowej ma złożoność $O(1)$.
|
|
|
W implementacji tablicowej listy, jak realizowana jest operacja DELETE(k)? inizia ad imparare
|
|
Poprzez przesunięcie wszystkich elementów od pozycji k+1 do końca listy o jedną pozycję w lewo.
|
|
|
Co przechowuje każdy element listy pojedynczo wiązanej? inizia ad imparare
|
|
Przechowuje dane (dataItem) oraz wskaźnik (next) do następnego elementu.
|
|
|
Dlaczego w liście pojedynczo wiązanej operacja PREVIOUS(k) ma złożoność $O(n)$? inizia ad imparare
|
|
Ponieważ aby znaleźć element poprzedzający 'k', należy przejść listę od początku (head).
|
|
|
Jaka jest główna zaleta listy podwójnie wiązanej w porównaniu do pojedynczo wiązanej? inizia ad imparare
|
|
Umożliwia wykonanie operacji PREVIOUS w czasie $O(1)$ dzięki wskaźnikowi do poprzedniego elementu (prev).
|
|
|
Co to jest 'stos' (stack) jako ADT? inizia ad imparare
|
|
Jest to ciąg elementów, dla którego operacje wstawiania i usuwania są dozwolone tylko po jednej stronie (LIFO - Last-In, First-Out).
|
|
|
Jak nazywa się operacja wstawienia elementu na stos? inizia ad imparare
|
|
|
|
|
Jak nazywa się operacja usunięcia elementu ze stosu? inizia ad imparare
|
|
|
|
|
Operacja _____ zwraca element ze szczytu stosu, ale go nie usuwa. inizia ad imparare
|
|
|
|
|
Jaka jest złożoność czasowa operacji PUSH i POP dla implementacji tablicowej i listowej stosu? inizia ad imparare
|
|
Złożoność obu operacji dla obu implementacji wynosi $O(1)$.
|
|
|
Co to jest 'kolejka' (queue) jako ADT? inizia ad imparare
|
|
Jest to ciąg elementów, w którym elementy wstawia się na jednym końcu (tail), a usuwa z drugiego (head) (FIFO - First-In, First-Out).
|
|
|
Jak nazywa się operacja wstawienia elementu do kolejki? inizia ad imparare
|
|
|
|
|
Jak nazywa się operacja usunięcia elementu z kolejki? inizia ad imparare
|
|
|
|
|
W tablicowej implementacji kolejki używa się tablicy _____, aby uniknąć przesuwania elementów. inizia ad imparare
|
|
|
|
|
Dlaczego w listowej implementacji kolejki potrzebne są wskaźniki na początek (head) i koniec (tail)? inizia ad imparare
|
|
Aby operacje ENQUEUE (na końcu) i DEQUEUE (z początku) mogły być wykonane w czasie $O(1)$.
|
|
|
Jaka jest złożoność czasowa operacji ENQUEUE i DEQUEUE dla implementacji tablicowej (cyklicznej) i listowej kolejki? inizia ad imparare
|
|
Złożoność obu operacji dla obu implementacji wynosi $O(1)$.
|
|
|
W czym pomaga 'wartownik' (sentinel) w implementacji list wiązanych? inizia ad imparare
|
|
Upraszcza warunki brzegowe (np. dla pustej listy, wstawiania na początek/koniec), eliminując potrzebę sprawdzania wskaźników NULL.
|
|
|
Opisz działanie algorytmu wyszukiwania liniowego. inizia ad imparare
|
|
Algorytm polega na sekwencyjnym sprawdzaniu każdego elementu w zbiorze danych, aż do znalezienia szukanego elementu lub do końca zbioru.
|
|
|
Jakie jest główne założenie dotyczące danych dla algorytmu wyszukiwania binarnego? inizia ad imparare
|
|
Dane muszą być posortowane.
|
|
|
Opisz ogólną zasadę działania wyszukiwania binarnego. inizia ad imparare
|
|
Algorytm porównuje szukany element z elementem środkowym i na podstawie wyniku porównania eliminuje połowę przeszukiwanego zbioru.
|
|
|
Jaka jest złożoność czasowa wyszukiwania binarnego? inizia ad imparare
|
|
Złożoność czasowa wyszukiwania binarnego wynosi $O(\log_2 n)$.
|
|
|
Czym różni się wyszukiwanie interpolacyjne od binarnego w sposobie wyznaczania następnego punktu do sprawdzenia? inizia ad imparare
|
|
Wyszukiwanie interpolacyjne estymuje pozycję szukanego elementu na podstawie jego wartości, a nie tylko dzieli zbiór na pół.
|
|
|
Co to jest operacja RETRIEVE dla listy ADT? inizia ad imparare
|
|
Zwraca element z podanej pozycji 'k' na liście L.
|
|
|
W implementacji stosu na liście, operacja PUSH odpowiada operacji _____ na liście. inizia ad imparare
|
|
PREPEND (wstawienie na początek)
|
|
|
W implementacji stosu na liście, operacja POP odpowiada operacji _____ na liście. inizia ad imparare
|
|
DELETE FIRST (usunięcie pierwszego elementu)
|
|
|
W liście dwukierunkowej z wartownikiem, jak sprawdzić, czy lista jest pusta? inizia ad imparare
|
|
Lista jest pusta, jeśli wskaźnik 'next' wartownika wskazuje na samego siebie (head->next == head).
|
|
|
Jaka jest maksymalna wysokość drzewa binarnego o 'n' węzłach? inizia ad imparare
|
|
Maksymalna wysokość wynosi $h = n - 1$, co odpowiada drzewu zdegenerowanemu (liście).
|
|
|
Co to jest 'potomek właściwy' (proper descendant) węzła 'n'? inizia ad imparare
|
|
Jest to dowolny potomek węzła 'n', który jest różny od samego 'n'.
|
|
|
W drzewie BST, czym jest 'poprzednik' (predecessor) węzła 'n'? inizia ad imparare
|
|
Jest to węzeł o największej wartości spośród wszystkich wartości mniejszych od wartości węzła 'n'.
|
|
|
W drzewie BST, gdzie znajduje się poprzednik węzła 'n', jeśli 'n' ma lewe poddrzewo? inizia ad imparare
|
|
Poprzednik to węzeł o maksymalnej wartości w lewym poddrzewie węzła 'n'.
|
|
|
W drzewie AVL, przypadek rotacji RL jest stosowany, gdy węzeł jest niezrównoważony na prawo (bf = -2), a jego prawy syn ma współczynnik bf równy _____. inizia ad imparare
|
|
|
|
|
W drzewie AVL, przypadek rotacji LR jest stosowany, gdy węzeł jest niezrównoważony na lewo (bf = 2), a jego lewy syn ma współczynnik bf równy _____. inizia ad imparare
|
|
|
|
|
Jaka jest złożoność czasowa operacji CLEAR dla stosu/kolejki w implementacji tablicowej? inizia ad imparare
|
|
$O(1)$, ponieważ polega jedynie na zresetowaniu indeksów/rozmiaru (dane fizycznie nie są usuwane).
|
|
|
Jaka jest złożoność czasowa operacji CLEAR dla stosu/kolejki/listy w implementacji wskaźnikowej? inizia ad imparare
|
|
$O(n)$, ponieważ należy przejść przez wszystkie elementy i zwolnić pamięć dla każdego z nich.
|
|
|
Co oznacza, że złożoność czasowa operacji wynosi $O(1)$? inizia ad imparare
|
|
Oznacza to, że czas wykonania operacji jest stały i niezależny od liczby elementów w strukturze danych.
|
|
|
W implementacji tablicowej kolejki, funkcja `addone(i)` dla tablicy o pojemności `capacity` jest często realizowana jako _____. inizia ad imparare
|
|
|
|
|
Co jest główną wadą tablicowej implementacji struktur danych takich jak listy, stosy czy kolejki? inizia ad imparare
|
|
Mają z góry ustaloną, stałą pojemność, co może prowadzić do marnowania pamięci lub przepełnienia.
|
|
|
Co jest główną wadą implementacji listowej (wskaźnikowej)? inizia ad imparare
|
|
Brak bezpośredniego dostępu do elementu o zadanym indeksie (wymaga przejścia od początku), co skutkuje złożonością $O(n)$ dla tej operacji.
|
|
|
Z jakich pól składa się węzeł w 'wskaźnikowej' reprezentacji drzewa binarnego? inizia ad imparare
|
|
Zazwyczaj z pola na dane (dataItem) oraz wskaźników na lewego syna (left), prawego syna (right) i opcjonalnie ojca (parent).
|
|
|
W jaki sposób operacja INSERT w drzewie BST zachowuje jego właściwości? inizia ad imparare
|
|
Nowy węzeł jest zawsze wstawiany jako liść w odpowiednim miejscu, zgodnie z zasadami porządkowania BST.
|
|
|
Jakie operacje na drzewie AVL mogą naruszyć jego własność zrównoważenia? inizia ad imparare
|
|
Operacje INSERT i DELETE.
|
|
|
Złożoność czasowa pojedynczej rotacji w drzewie AVL wynosi _____. inizia ad imparare
|
|
|
|
|
Jaka jest różnica między operacją `FRONT/PEEK` a `DEQUEUE` w kolejce? inizia ad imparare
|
|
`FRONT/PEEK` zwraca pierwszy element bez usuwania go, podczas gdy `DEQUEUE` usuwa pierwszy element (zwykle go nie zwracając).
|
|
|
Jakie dwa warunki musi spełniać drzewo AVL? inizia ad imparare
|
|
Musi być binarnym drzewem poszukiwań (BST), w
|
|
|
