Struktury danych: karta pracy z odpowiedziami

W binarnym drzewie poszukiwań wartości w lewym poddrzewie węzła są:

1. ARówne wartości węzła
2. BW losowej kolejności
3. CWiększe od wartości węzła
4. DMniejsze od wartości węzła

Czym jest deque (kolejka dwustronna)?

1. AKolejką, która pozwala usuwać elementy tylko z końca
2. BDwiema oddzielnymi kolejkami dzielącymi jedną tablicę
3. CStrukturą pozwalającą wstawiać i usuwać elementy na obu końcach
4. DKolejką posortowaną według priorytetu

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

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

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

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

Drzewo trie (drzewo prefiksowe) jest szczególnie wydajne przy:

1. AWyszukiwaniu po prefiksie, np. autouzupełnianiu
2. BZnajdowaniu najkrótszych ścieżek
3. CSortowaniu liczb
4. DPrzechowywaniu macierzy

Jaki warunek zrównoważenia utrzymuje drzewo AVL w każdym węźle?

1. AWysokości lewego i prawego poddrzewa różnią się co najwyżej o 1
2. BOba poddrzewa każdego węzła zawierają dokładnie tyle samo węzłów
3. CKażdy węzeł jest pokolorowany na czerwono lub czarno
4. DWszystkie liście są na dokładnie tej samej głębokości

Drzewo przedziałowe (segment tree) służy zwykle do:

1. AImplementacji stosu
2. BPrzechowywania krawędzi grafu
3. COdpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
4. DAlfabetycznego sortowania napisów przez przechowywanie każdego prefiksu w osobnym węźle drzewa

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

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