Struktury danych: karta pracy z odpowiedziami

Czym jest graf ważony?

1. AGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
2. BGrafem, który ma więcej krawędzi niż wierzchołków
3. CGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
4. DGrafem przechowywanym na dysku

Co przechowuje się dla każdego wierzchołka w reprezentacji grafu za pomocą list sąsiedztwa?

1. AWiersz V wartości logicznych
2. BListę jego sąsiednich wierzchołków
3. CNajkrótszą ścieżkę do każdego innego wierzchołka
4. DŁączną liczbę krawędzi w grafie

Czym jest kolizja w tablicy mieszającej?

1. AOdwzorowaniem dwóch różnych kluczy na ten sam indeks
2. BWyczerpaniem pamięci przez tablicę
3. CDwukrotnym zapisaniem dwóch równych kluczy
4. DSytuacją, w której klucza w ogóle nie da się zahaszować

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

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

Co się dzieje, gdy tablica mieszająca wykonuje rehashing po przekroczeniu progu współczynnika zapełnienia?

1. ANajstarsze klucze są usuwane, by zrobić miejsce
2. BTylko kolidujące klucze są przenoszone na nową listę nadmiarową na końcu tablicy
3. CAlokuje się większą tablicę i ponownie wstawia każdy klucz
4. DIstniejące klucze są sortowane w miejscu

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

1. AWstawiania
2. BRosnącej (posortowanej)
3. CPoziomami
4. DZawsze malejącej

Wstawienie klucza do drzewa AVL sprawia, że lewe poddrzewo pewnego węzła staje się zbyt wysokie, a nowy klucz trafił do lewego poddrzewa jego lewego dziecka (przypadek lewo-lewo). Jaką naprawę się stosuje?

1. APojedynczą rotację w lewo w niezrównoważonym węźle
2. BRotację w lewo w dziecku, a potem rotację w prawo w węźle
3. CPojedynczą rotację w prawo w niezrównoważonym węźle
4. DPrzekolorowanie węzła i jego dziecka

Którą własność musi spełniać drzewo czerwono-czarne?

1. AKażdy węzeł musi być czerwony
2. BKażdy czerwony węzeł musi mieć czerwone dzieci, więc czerwone węzły zawsze tworzą nieprzerwane łańcuchy aż do liści
3. CKorzeń musi być czerwony
4. DKażda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów