Struktury danych: karta pracy z odpowiedziami

Czym jest korzeń drzewa?

1. ANajwyższy węzeł, który nie ma rodzica
2. BDowolny węzeł w środku
3. CWęzeł bez dzieci
4. DWęzeł o największej wartości

Głębokość węzła w drzewie to:

1. ALiczba krawędzi od tego węzła do najgłębszego liścia
2. BLiczba dzieci tego węzła
3. CLiczba krawędzi od korzenia do tego węzła
4. DLiczba węzłów w jego poddrzewie

Jaka jest cecha definiująca zbiór jako abstrakcyjny typ danych?

1. APrzechowuje elementy w kolejności posortowanej
2. BPrzechowuje pary klucz–wartość
3. CPrzechowuje elementy bez duplikatów
4. DPozwala na dostęp tylko z jednego końca

Której struktury danych używa przeszukiwanie w głąb (DFS) w wersji iteracyjnej?

1. AKopca
2. BKolejki
3. CWyłącznie tablicy mieszającej
4. DStosu

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

1. AO(log n), z powodu wyszukiwania binarnego
2. BO(n²), bo każdy element przesuwa się n razy
3. CO(1), bo indeks jest znany
4. DO(n), bo dalsze elementy trzeba przesunąć

Przejście in-order (poprzeczne) binarnego drzewa poszukiwań odwiedza klucze w kolejności:

1. ARosnącej (posortowanej)
2. BZawsze malejącej
3. CPoziomami
4. DWstawiania

Jaki jest koszt czasowy i dodatkowy pamięciowy odwrócenia listy jednokierunkowej w miejscu?

1. ACzas O(n) i dodatkowa pamięć O(n)
2. BCzas O(n log n) i dodatkowa pamięć O(1)
3. CCzas O(n) i dodatkowa pamięć O(1)
4. DCzas O(1) i dodatkowa pamięć O(1)

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. BKopiec minimalny przechowujący wszystkie n wartości, z którego na końcu zdejmuje się k najmniejszych
3. CPosortowana tablica wszystkich n wartości
4. DKolejka FIFO ostatnich k wartości