Struktury danych: karta pracy z odpowiedziami

Czym jest kolizja w tablicy mieszającej?

1. AWyczerpaniem pamięci przez tablicę
2. BSytuacją, w której klucza w ogóle nie da się zahaszować
3. CDwukrotnym zapisaniem dwóch równych kluczy
4. DOdwzorowaniem dwóch różnych kluczy na ten sam indeks

Czym jest graf skierowany?

1. AGrafem, którego krawędzie mają kierunek od jednego wierzchołka do drugiego
2. BGrafem, którego wszystkie krawędzie mają wagi
3. CGrafem, w którym każda para różnych wierzchołków jest połączona krawędzią
4. DGrafem bez cykli

W liście jednokierunkowej każdy węzeł zawiera:

1. ADane i referencje do wszystkich pozostałych węzłów
2. BDane i indeks
3. CDane i referencję do następnego węzła
4. DTylko dane

Tablica mieszająca o rozmiarze 7 używa h(k) = k mod 7 i próbkowania liniowego. Gdzie zostanie zapisane 17 po wstawieniu 10?

1. APod indeksem 4
2. BPod indeksem 3
3. CPod indeksem 0
4. DPod indeksem 6

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

1. AKażdy wiersz ma dokładnie jedną jedynkę
2. BJest symetryczna względem głównej przekątnej
3. CNa jej głównej przekątnej zawsze są jedynki
4. DJest zawsze górnotrójkątna

Masz referencję do węzła w środku listy. W której liście możesz go usunąć w O(1)?

1. AW liście dwukierunkowej
2. BW liście jednokierunkowej
3. CW posortowanej tablicy
4. DW tablicy dynamicznej

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

1. ASortowanie tablicy i wyszukiwanie binarne
2. BWstawianie elementów na dowolnej pozycji
3. CZnajdowanie mediany w O(1)
4. DZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów

Jaka jest główna zaleta listy z przeskokami (skip list) nad posortowaną listą wiązaną?

1. AGwarantowane wyszukiwanie w O(1), bo każdy węzeł przechowuje wskaźnik do każdego innego węzła
2. BPrzechowuje klucze bez uporządkowania
3. COczekiwane wyszukiwanie w O(log n) dzięki kilku poziomom wskaźników do przodu
4. DNie zużywa dodatkowej pamięci