Struktury danych: karta pracy z odpowiedziami

Tablica mieszająca (hash table) przechowuje dane jako:

1. AWyłącznie posortowaną listę
2. BPary klucz–wartość lokalizowane przez funkcję mieszającą
3. CDrzewo z uporządkowanymi kluczami
4. DCiąg znaków o stałej długości

Co zawiera każdy węzeł listy dwukierunkowej?

1. ADane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
2. BDane i dwa wskaźniki: jeden do następnego węzła i jeden do węzła po nim
3. CDane i tylko wskaźnik na następny węzeł
4. DDwie kopie danych i jeden wskaźnik

Co definiuje drzewo binarne?

1. AKażdy węzeł przechowuje liczbę binarną
2. BDrzewo ma dokładnie dwa poziomy
3. CKażdy węzeł ma co najwyżej dwoje dzieci
4. DKażdy węzeł ma dokładnie dwoje dzieci

Jaka jest pesymistyczna wysokość binarnego drzewa poszukiwań z n węzłami, jeśli klucze są wstawiane w kolejności posortowanej?

1. Alog₂ n
2. B1
3. Cn (drzewo staje się listą wiązaną)
4. D√n

Dlaczego kopiec binarny można przechowywać w tablicy bez żadnych wskaźników?

1. AWszystkie klucze w kopcu są równe
2. BKopce nigdy nie zawierają więcej niż 100 elementów
3. CJest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy
4. DTablice automatycznie utrzymują klucze w kolejności posortowanej, więc wskaźniki nie są potrzebne

Jak wstawia się nowy element do kopca binarnego?

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

Dlaczego B-drzewa są używane w bazach danych i systemach plików?

1. APrzechowują dane nieposortowane
2. BZajmują mniej pamięci niż jakakolwiek tablica, więc cały indeks zawsze mieści się w pamięci głównej
3. CDuży stopień rozgałęzienia utrzymuje drzewo płytkim, ograniczając wolne odczyty z dysku
4. DNie wymagają równoważenia

Dlaczego w tablicy mieszającej z adresowaniem otwartym usuwanie wykonuje się często za pomocą znacznika „nagrobka” (tombstone)?

1. ANagrobki przyspieszają haszowanie
2. BUsunięte klucze muszą być przechowywane na zawsze ze względów bezpieczeństwa, więc miejsc nigdy nie można użyć ponownie
3. CDzięki temu tablica staje się posortowana
4. DOpróżnienie miejsca mogłoby przerwać sekwencję sondowania dla innych kluczy