Struktury danych: karta pracy z odpowiedziami

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

1. ALista wiązana
2. BTablica mieszająca
3. CKolejka
4. DStos

Czym jest stopień wierzchołka w grafie nieskierowanym?

1. AJego pozycją na liście sąsiedztwa
2. BDługością najdłuższej ścieżki z niego wychodzącej
3. CLiczbą wierzchołków w grafie
4. DLiczbą krawędzi z nim połączonych

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

1. AW korzeniu
2. BNa ostatniej pozycji tablicy
3. CW skrajnie lewym liściu
4. DW którymś liściu, którego trzeba szukać

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

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

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

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

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

1. AWstawiania
2. BRosnącej (posortowanej)
3. CZawsze malejącej
4. DPoziomami

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

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

Klucze 5, 3, 8, 1 wstawia się w tej kolejności do pustego binarnego kopca minimalnego opartego na tablicy. Jak wygląda końcowa tablica?

1. A[1, 3, 8, 5]
2. B[1, 5, 8, 3]
3. C[3, 1, 8, 5]
4. D[1, 3, 5, 8]