→ AiSD → Start Learning / Flashcards Téléchargement MP3

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

AiSD

Vous devez vous connecter pour poster un commentaire.

plus