→ AiSD → Start Learning / Download MP3 Flashcards

Question		Answer
Czym jest drzewo ukorzenione (rooted tree)? start learning		Jest to drzewo puste lub węzeł (korzeń) zawierający listę poddrzew.
W terminologii drzew, co to jest 'syn' (child) węzła n1? start learning		Jest to korzeń jednego z poddrzew węzła n1.
Węzeł o stopniu 0 w drzewie nazywany jest _____. start learning		liściem (leaf).
Jaka jest definicja 'głębokości' (depth) węzła w drzewie? start learning		Jest to długość ścieżki od korzenia do tego węzła.
Czym jest 'wysokość' (height) drzewa? start learning		Jest to maksymalna głębokość dowolnego węzła w drzewie.
Co odróżnia drzewo uporządkowane od nieuporządkowanego? start learning		W drzewie uporządkowanym synowie każdego węzła wewnętrznego są liniowo uporządkowani.
Zdefiniuj drzewo binarne. start learning		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? start learning		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? start learning		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? start learning		Najpierw lewe poddrzewo, potem prawe poddrzewo, a na końcu korzeń.
Jaka jest minimalna wysokość 'h' drzewa binarnego o 'n' węzłach? start learning		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)? start learning		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)? start learning		Pozycja prawego syna to $2 * n + 2$.
Jaka jest złożoność czasowa operacji SIZE i HEIGHT dla wskaźnikowej implementacji drzewa binarnego? start learning		Złożoność czasowa obu operacji wynosi $O(n)$.
Zdefiniuj Binarne Drzewo Poszukiwań (BST). start learning		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? start learning		W najgorszym przypadku (drzewo zdegenerowane) złożoność wynosi $O(n)$.
Jak w drzewie BST znaleźć węzeł o minimalnej wartości? start learning		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? start learning		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? start learning		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). start learning		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'.
Co to jest drzewo AVL? start learning		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? start learning		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? start learning		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? start learning		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? start learning		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? start learning		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? start learning		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? start learning		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? start learning		Złożoność czasowa tych operacji wynosi $O(\log_2 n)$.
Czym jest 'lista' jako abstrakcyjny typ danych (ADT)? start learning		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? start learning		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? start learning		Operacja PREPEND w implementacji listowej ma złożoność $O(1)$.
W implementacji tablicowej listy, jak realizowana jest operacja DELETE(k)? start learning		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? start learning		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)$? start learning		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? start learning		Umożliwia wykonanie operacji PREVIOUS w czasie $O(1)$ dzięki wskaźnikowi do poprzedniego elementu (prev).
Co to jest 'stos' (stack) jako ADT? start learning		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? start learning		PUSH.
Jak nazywa się operacja usunięcia elementu ze stosu? start learning		POP.
Operacja _____ zwraca element ze szczytu stosu, ale go nie usuwa. start learning		TOP (lub PEEK).
Jaka jest złożoność czasowa operacji PUSH i POP dla implementacji tablicowej i listowej stosu? start learning		Złożoność obu operacji dla obu implementacji wynosi $O(1)$.
Co to jest 'kolejka' (queue) jako ADT? start learning		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? start learning		ENQUEUE.
Jak nazywa się operacja usunięcia elementu z kolejki? start learning		DEQUEUE.
W tablicowej implementacji kolejki używa się tablicy _____, aby uniknąć przesuwania elementów. start learning		cyklicznej.
Dlaczego w listowej implementacji kolejki potrzebne są wskaźniki na początek (head) i koniec (tail)? start learning		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? start learning		Złożoność obu operacji dla obu implementacji wynosi $O(1)$.
W czym pomaga 'wartownik' (sentinel) w implementacji list wiązanych? start learning		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. start learning		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? start learning		Dane muszą być posortowane.
Opisz ogólną zasadę działania wyszukiwania binarnego. start learning		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? start learning		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? start learning		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? start learning		Zwraca element z podanej pozycji 'k' na liście L.
W implementacji stosu na liście, operacja PUSH odpowiada operacji _____ na liście. start learning		PREPEND (wstawienie na początek)
W implementacji stosu na liście, operacja POP odpowiada operacji _____ na liście. start learning		DELETE FIRST (usunięcie pierwszego elementu)
W liście dwukierunkowej z wartownikiem, jak sprawdzić, czy lista jest pusta? start learning		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? start learning		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'? start learning		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'? start learning		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? start learning		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 _____. start learning		1
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 _____. start learning		-1
Jaka jest złożoność czasowa operacji CLEAR dla stosu/kolejki w implementacji tablicowej? start learning		$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? start learning		$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)$? start learning		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 _____. start learning		(i + 1) % capacity
Co jest główną wadą tablicowej implementacji struktur danych takich jak listy, stosy czy kolejki? start learning		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)? start learning		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? start learning		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? start learning		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? start learning		Operacje INSERT i DELETE.
Złożoność czasowa pojedynczej rotacji w drzewie AVL wynosi _____. start learning		$O(1)$.
Jaka jest różnica między operacją `FRONT/PEEK` a `DEQUEUE` w kolejce? start learning		`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? start learning		Musi być binarnym drzewem poszukiwań (BST), w

AiSD

You must sign in to write a comment

More