→ AiSD → Rozpocznij Naukę / Ściągnij Fiszki MP3

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

AiSD

Musisz się zalogować, by móc napisać komentarz.