Struktury Danych, Analiza Złożoności (Big-O) i Kluczowe Algorytmy

Powtórka na poziomie studiów pierwszego stopnia, wymagająca podstaw programowania: 32 fiszki o tablicach, listach, haszowaniu, drzewach, kopcach, trie, Union–Find, filtrach Blooma i złożoności.

Category
Computer Science
Level
basic
Languages
pl → pl
Cards
32
Markdown
Struktury Danych, Analiza Złożoności (Big-O) i Kluczowe Algorytmy (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Czym jest współczynnik zapełnienia tablicy haszującej i dlaczego można ją powiększać?α = n/m: n wpisów i m kubełków lub komórek. Przekroczenie progu implementacji może spowodować powiększenie i ponowne haszowanie; 0,75 nie jest wartością uniwersalną.
2Czym różnią się kompresja ścieżek, łączenie według rangi i według rozmiaru?Kompresja kieruje odwiedzone węzły do korzenia. Według rangi korzeń o niższej randze trafia pod wyższy; według rozmiaru mniejszy zbiór pod większy. Ranga nie musi równać się aktualnej wysokości.
3Porównaj wstawienie na początku i dostęp przez indeks w liście jednokierunkowej oraz tablicy dynamicznej.Lista: wstawienie na początku O(1), dostęp przez indeks O(n). Tablica: wstawienie na początku O(n), dostęp przez indeks O(1); wstawienie z przodu przesuwa elementy.
4Jak wyszukiwanie, wstawianie i usuwanie w BST zależą od wysokości h?Kosztują O(h). Drzewo zrównoważone ma h = O(log n), a łańcuch h = O(n). Oczekiwane O(log n) wymaga założeń, np. losowej kolejności wstawiania.
5Gdzie są rodzic i dzieci węzła i w tablicy kopca długości n indeksowanej od zera?Rodzic: ⌊(i−1)/2⌋ dla i>0. Dzieci: 2i+1 i 2i+2, o ile indeksy są mniejsze od n. Indeks 0 nie ma rodzica.
6Ile kosztuje budowa kopca od dołu z n elementów?O(n). Większość węzłów leży blisko liści i wymaga niewielu przesunięć w dół; suma pracy według wysokości węzłów jest liniowa.
7Jak naprawić nierównowagę lewo-prawo po wstawieniu do AVL?Najpierw wykonaj obrót lewego dziecka w lewo, potem niezrównoważonego węzła w prawo.
8Jak kolejka w tablicy cyklicznej unika przesuwania po pobraniu elementu?Indeksy początku i końca zawijają się modulo pojemność. Pobranie przesuwa indeks początku, więc wolne komórki można wykorzystać ponownie bez przenoszenia pozostałych elementów.
9Jak przejście poziomami odwiedza drzewo binarne?Kolejka FIFO pozwala odwiedzać kolejne poziomy głębokości. Dodanie lewego dziecka przed prawym zapewnia kolejność od lewej do prawej.
10Jakie są oczekiwane i pesymistyczne koszty operacji w tablicy haszującej z łańcuchowaniem?Przy ograniczonym zapełnieniu, dobrym rozproszeniu i stałym koszcie operacji na kluczach wyszukiwanie/usuwanie ma oczekiwany koszt O(1). Wstawianie przy wzroście geometrycznym ma oczekiwany koszt zamortyzowany O(1). Łańcuch n kolidujących kluczy może dać O(n).
11Jaki jest zamortyzowany koszt union/find z kompresją ścieżek i łączeniem według rangi?O(α(n)) na operację, gdzie α to odwrotność funkcji Ackermanna, a n to liczba elementów. Inicjalizacja kosztuje O(n); ograniczenie dotyczy ciągu operacji, nie stałego kosztu pesymistycznego każdego wywołania.
12Jakie są kolejności przejść preorder, inorder i postorder w drzewie binarnym?Preorder: węzeł → lewe → prawe. Inorder: lewe → węzeł → prawe. Postorder: lewe → prawe → węzeł.
13Co robią find i union w strukturze zbiorów rozłącznych?find(x) zwraca reprezentanta zbioru x. union(x,y) łączy ich zbiory, jeśli są różne; jeśli już są tym samym zbiorem, podział się nie zmienia.
14Jak działa stos i kiedy jego operacje kosztują O(1)?LIFO: ostatnio dodany element jest zdejmowany pierwszy. Na początku listy operacje dodania, zdjęcia i odczytu szczytu kosztują O(1); zmiana rozmiaru tablicy może zwiększyć koszt pojedynczego dodania do O(n).
15Jaki jest warunek równowagi AVL?W każdym węźle wysokość(lewe) − wysokość(prawe) ∈ {−1, 0, 1}. Drzewo spełnia też niezmiennik porządku BST.
16Jakie reguły kolorów utrzymują równowagę czerwono-czarnego BST?Węzły są czerwone lub czarne; korzeń i liście NIL są czarne. Czerwony węzeł nie ma czerwonych dzieci. Każda ścieżka od węzła do potomnego liścia NIL zawiera tyle samo czarnych węzłów. Daje to wysokość O(log n).
17Jakie dwie właściwości definiują binarny kopiec minimalny?Jest kompletnym drzewem binarnym, a klucz rodzica nie przewyższa kluczy jego dzieci. Korzeń zawiera zatem minimum.
18Co oznacza f(n) ∈ O(g(n)) dla nieujemnych funkcji f i g?Istnieją stałe c > 0 i n₀ ≥ 0 takie, że f(n) ≤ c·g(n) dla każdego n ≥ n₀.
19Czym jest trie i kiedy wyszukanie klucza długości L kosztuje O(L)?Drzewo prefiksowe zapisuje klucze na ścieżkach znaków, oznaczając kompletne klucze. Wyszukiwanie kosztuje O(L), jeśli każde przejście dla następnego znaku kosztuje O(1).
20Dlaczego dostęp przez indeks w tablicy o stałym rozmiarze kosztuje O(1)?Komórki jednakowego rozmiaru leżą kolejno w pamięci: adres(i) = baza + i·rozmiar_komórki. Zakładamy stały czas obliczania adresu.
21Jaki jest zamortyzowany koszt dopisania na końcu tablicy dynamicznej przy podwajaniu pojemności?O(1) na dopisanie. Zmiana rozmiaru może kosztować O(n), ale n dopisań od pustej tablicy kosztuje łącznie O(n).
22Czym różnią się O, Ω i Θ?Oznaczają odpowiednio asymptotyczne ograniczenie górne, dolne i dokładne co do rzędu. Opisują określoną funkcję kosztu; samo O nie oznacza przypadku pesymistycznego.
23Dlaczego lista dwukierunkowa może usunąć wskazany węzeł w O(1)?Odnośniki do poprzednika i następnika pozwalają bezpośrednio połączyć sąsiadów. W razie potrzeby aktualizuje się początek/koniec; nie trzeba szukać poprzednika.
24Jaki niezmiennik porządku definiuje binarne drzewo wyszukiwania (BST) o różnych kluczach?Dla każdego węzła wszystkie klucze lewego poddrzewa są mniejsze, a prawego większe. Reguła obowiązuje rekurencyjnie.
25Czym różnią się próbkowanie liniowe i kwadratowe w adresowaniu otwartym?Wpisy pozostają w tablicy. Dla rozmiaru m i indeksu początkowego h sprawdza się odpowiednio (h+i) mod m oraz (h+c₁i+c₂i²) mod m. Próbkowanie kwadratowe wymaga odpowiednich parametrów.
26Uporządkuj tempa wzrostu od najwolniejszego do najszybszego przy n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.Asymptotycznie: 1 < log n < n < n log n < n² < 2ⁿ < n!.
27Jaka jest kolejność dostępu i typowe koszty operacji kolejki?FIFO: dodawanie na końcu, pobieranie z początku. Obie operacje kosztują O(1) z odnośnikami do początku/końca lub w buforze cyklicznym o stałej pojemności; przesuwanie tablicy daje pobieranie O(n).
28Jak łańcuchowanie rozwiązuje kolizje haszowania?Każdy kubełek zawiera zbiór wpisów o tym indeksie, często listę wiązaną. Różne klucze w tym samym kubełku pozostają oddzielnymi wpisami.
29Jakie odpowiedzi daje filtr Blooma dopuszczający tylko wstawianie?Wynik negatywny oznacza, że elementu nie wstawiono; pozytywny, że mógł zostać wstawiony. Hasze ustawiają bity w tablicy: możliwe są wyniki fałszywie dodatnie, ale nie fałszywie ujemne przy nienaruszonym stanie.
30Jakie cechy powinna mieć funkcja haszująca do wyszukiwania w tablicy?Powinna być deterministyczna i dobrze rozpraszać spodziewane klucze. Haszowanie klucza o stałym rozmiarze może kosztować O(1); nowego napisu długości L zwykle O(L).
31Co daje przejście inorder drzewa BST o różnych kluczach?Wszystkie klucze w porządku ściśle rosnącym, odwiedzając n węzłów w O(n).
32Ile kosztują wstawienie, usunięcie korzenia i odczyt korzenia kopca binarnego?Odpowiednio O(log n), O(log n) i O(1), jeśli nie trzeba zmieniać rozmiaru tablicy. Taka zmiana może kosztować O(n).