Struktury danych: karta pracy z odpowiedziami

Czym jest liść w drzewie?

1. AWęzłem bez rodzica
2. BWęzłem o największej wartości
3. CWęzłem z dokładnie jednym dzieckiem
4. DWęzłem bez dzieci

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

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

Która struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

1. AStos
2. BKolejka
3. CTablica mieszająca
4. DLista wiązana

Jaki jest maksymalny możliwy współczynnik zapełnienia tablicy mieszającej z adresowaniem otwartym?

1. ANie ma maksimum
2. B0,5
3. C1
4. D2

Do czego służy węzeł wartownika (sentinel, węzeł pozorny) w liście wiązanej?

1. ASprawia, że lista jest posortowana
2. BPrzechowuje liczbę elementów
3. CUpraszcza kod, usuwając przypadki szczególne na początku lub końcu listy
4. DZapobiega wydłużaniu się listy ponad ustaloną maksymalną liczbę węzłów

Którego abstrakcyjnego typu danych używa algorytm Dijkstry do wyboru następnego wierzchołka do przetworzenia?

1. AStosu
2. BKolejki priorytetowej typu min
3. CKolejki FIFO
4. DZbioru bez uporządkowania

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

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

W BST z korzeniem 50, lewym poddrzewem 30 (dzieci 20, 40) i prawym poddrzewem 70 (dzieci 60, 80) usuwa się korzeń przy użyciu następnika w porządku inorder. Który klucz zostaje nowym korzeniem?

1. A80
2. B60
3. C70
4. D40