# 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.

- **Canonical URL:** https://flashcards.world/flashcards/sets/db0317b7-1dbc-4325-a569-7b2d28e4a793/
- **Markdown URL:** https://flashcards.world/flashcards/sets/db0317b7-1dbc-4325-a569-7b2d28e4a793.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** pl → pl
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Czym 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ą. |  |  |
| 2 | Czym 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. |  |  |
| 3 | Poró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. |  |  |
| 4 | Jak 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. |  |  |
| 5 | Gdzie 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. |  |  |
| 6 | Ile 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. |  |  |
| 7 | Jak 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. |  |  |
| 8 | Jak 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. |  |  |
| 9 | Jak 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. |  |  |
| 10 | Jakie 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). |  |  |
| 11 | Jaki 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. |  |  |
| 12 | Jakie 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ł. |  |  |
| 13 | Co 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. |  |  |
| 14 | Jak 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). |  |  |
| 15 | Jaki 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. |  |  |
| 16 | Jakie 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). |  |  |
| 17 | Jakie 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. |  |  |
| 18 | Co 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₀. |  |  |
| 19 | Czym 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). |  |  |
| 20 | Dlaczego 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. |  |  |
| 21 | Jaki 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). |  |  |
| 22 | Czym 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. |  |  |
| 23 | Dlaczego 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. |  |  |
| 24 | Jaki 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. |  |  |
| 25 | Czym 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. |  |  |
| 26 | Uporzą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!. |  |  |
| 27 | Jaka 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). |  |  |
| 28 | Jak ł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. |  |  |
| 29 | Jakie 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. |  |  |
| 30 | Jakie 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). |  |  |
| 31 | Co 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). |  |  |
| 32 | Ile 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). |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/db0317b7-1dbc-4325-a569-7b2d28e4a793/).
