Struktury danych: karta pracy z odpowiedziami

Czym jest kolizja w tablicy mieszającej?

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

Graf składa się z:

1. AWierszy i kolumn
2. BTylko korzenia i liści
3. CWyłącznie kluczy i skrótów
4. DWierzchołków (węzłów) połączonych krawędziami

Co przechowuje mapa (słownik)?

1. APary klucz–wartość z unikalnymi kluczami
2. BTylko wartości w kolejności wstawiania
3. CWartości posortowane według wielkości
4. DPary równych kluczy

Jak wstawia się nowy element do kopca binarnego?

1. AWstawia się go na właściwą posortowaną pozycję, przesuwając o jedno miejsce w prawo wszystkie większe elementy
2. BUmieszcza się go w korzeniu i przesuwa w dół
3. CBuduje się cały kopiec od nowa
4. DUmieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca

Ile węzłów ma doskonałe drzewo binarne o wysokości h, gdy wysokość liczy się w krawędziach?

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

Gdzie w kopcu binarnym przechowywanym w tablicy od indeksu 0 znajduje się rodzic węzła o indeksie i?

1. APod indeksem 2i + 1
2. BPod indeksem ⌊i / 2⌋ + 1
3. CPod indeksem i − 1
4. DPod indeksem ⌊(i − 1) / 2⌋

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

1. AZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy
2. BZamianę go z korzeniem
3. CZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
4. DUsunięcie całego poddrzewa

Dlaczego ze standardowego filtru Blooma nie można po prostu usuwać elementów przez zerowanie ich bitów?

1. ATe bity mogą należeć także do innych elementów, co spowodowałoby wyniki fałszywie negatywne
2. BUsuwanie zwiększyłoby odsetek wyników fałszywie pozytywnych do 100%
3. CFiltry Blooma przechowują całe elementy, których po zahaszowaniu nie da się ponownie zlokalizować
4. DBitów w filtrze Blooma nie można zmieniać po jego utworzeniu