Struktury danych: karta pracy z odpowiedziami

Która struktura jest zwykle używana do implementacji kolejki priorytetowej?

1. ANieuporządkowana lista jednokierunkowa
2. BCiąg znaków
3. CKopiec
4. DStos

Czym są węzły rodzeństwa (siblings) w drzewie?

1. AWęzłem i jego rodzicem
2. BWęzłami, które nie mają dzieci
3. CWęzłami na tej samej głębokości w różnych poddrzewach
4. DWęzłami, które mają tego samego rodzica

Graf składa się z:

1. AWierszy i kolumn
2. BWyłącznie kluczy i skrótów
3. CTylko korzenia i liści
4. DWierzchołków (węzłów) połączonych krawędziami

Masz referencję do węzła w środku listy. W której liście możesz go usunąć w O(1)?

1. AW liście dwukierunkowej
2. BW posortowanej tablicy
3. CW liście jednokierunkowej
4. DW tablicy dynamicznej

Której struktury danych używa działający program do śledzenia aktywnych wywołań funkcji i ich zmiennych lokalnych?

1. ATablicy mieszającej funkcji
2. BStosu wywołań
3. CBinarnego drzewa poszukiwań ramek
4. DKolejki pamięci sterty

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

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

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

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

Które stwierdzenie o sortowaniu przez kopcowanie (heapsort) jest poprawne?

1. AJest stabilne i wymaga O(n) dodatkowej pamięci
2. BSortuje w miejscu w pesymistycznym czasie O(n log n), ale nie jest stabilne
3. CWymaga binarnego drzewa poszukiwań jako dodatkowej pamięci, więc zużywa O(n) pamięci dodatkowej
4. DDziała w czasie O(n) dla każdych danych wejściowych