Struktury danych: karta pracy z odpowiedziami

Ile krawędzi ma drzewo o n węzłach?

1. An + 1
2. B2n
3. Cn
4. Dn − 1

Czym jest kolizja w tablicy mieszającej?

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

Co definiuje drzewo binarne?

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

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

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

Jak w kolejce cyklicznej przechowywanej w tablicy o pojemności n oblicza się następną pozycję po indeksie i?

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

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

1. A2^h
2. B2h + 1
3. Ch²
4. D2^h+1 − 1

Jaki jest czas działania przeszukiwania wszerz (BFS) w grafie o V wierzchołkach przechowywanym jako macierz sąsiedztwa?

1. AO(V²)
2. BO(E log V)
3. CO(V)
4. DO(V + E)

Musisz zachować k najmniejszych wartości ze strumienia n liczb, używając O(k) pamięci. Które podejście działa w czasie O(n log k)?

1. AKopiec maksymalny o rozmiarze k, którego korzeń zastępuje się, gdy pojawi się mniejsza wartość
2. BPosortowana tablica wszystkich n wartości
3. CKolejka FIFO ostatnich k wartości
4. DKopiec minimalny przechowujący wszystkie n wartości, z którego na końcu zdejmuje się k najmniejszych