Struktury danych: karta pracy z odpowiedziami

Co zawiera każdy węzeł listy dwukierunkowej?

1. ADane i dwa wskaźniki: jeden do następnego węzła i jeden do węzła po nim
2. BDane i tylko wskaźnik na następny węzeł
3. CDwie kopie danych i jeden wskaźnik
4. DDane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

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

Czym jest graf skierowany?

1. AGrafem, którego krawędzie mają kierunek od jednego wierzchołka do drugiego
2. BGrafem bez cykli
3. CGrafem, którego wszystkie krawędzie mają wagi
4. DGrafem, w którym każda para różnych wierzchołków jest połączona krawędzią

Gdzie w kopcu binarnym przechowywanym w tablicy od indeksu 0 znajduje się rodzic węzła o indeksie i?

1. APod indeksem 2i + 1
2. BPod indeksem ⌊(i − 1) / 2⌋
3. CPod indeksem ⌊i / 2⌋ + 1
4. DPod indeksem i − 1

Drzewo binarne ma korzeń 1 z lewym dzieckiem 2 i prawym dzieckiem 3; węzeł 2 ma dzieci 4 (lewe) i 5 (prawe). Jaki jest wynik przejścia preorder?

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C1 2 3 4 5
4. D4 2 5 1 3

Jak wstawia się nowy element do kopca binarnego?

1. ABuduje się cały kopiec od nowa
2. BUmieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
3. CUmieszcza się go w korzeniu i przesuwa w dół
4. DWstawia się go na właściwą posortowaną pozycję, przesuwając o jedno miejsce w prawo wszystkie większe elementy

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

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

Drzewo przedziałowe (segment tree) służy zwykle do:

1. AOdpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
2. BPrzechowywania krawędzi grafu
3. CAlfabetycznego sortowania napisów przez przechowywanie każdego prefiksu w osobnym węźle drzewa
4. DImplementacji stosu