Struktury danych: karta pracy z odpowiedziami

Wysokość drzewa definiuje się zwykle jako:

1. ALiczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
2. BLiczbę liści w drzewie
3. CLiczbę dzieci korzenia
4. DŁączną liczbę węzłów w drzewie, wliczając korzeń i każdy liść

W liście jednokierunkowej każdy węzeł zawiera:

1. ADane i indeks
2. BTylko dane
3. CDane i referencje do wszystkich pozostałych węzłów
4. DDane i referencję do następnego węzła

Czym jest graf ważony?

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

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

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

Dlaczego kopiec binarny można przechowywać w tablicy bez żadnych wskaźników?

1. ATablice automatycznie utrzymują klucze w kolejności posortowanej, więc wskaźniki nie są potrzebne
2. BKopce nigdy nie zawierają więcej niż 100 elementów
3. CWszystkie klucze w kopcu są równe
4. DJest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy

Węzeł binarnego drzewa poszukiwań ma prawe poddrzewo. Gdzie jest jego następnik w porządku inorder?

1. AZawsze w jego rodzicu
2. BW skrajnie lewym węźle jego prawego poddrzewa
3. CW skrajnie prawym węźle jego lewego poddrzewa
4. DZawsze w jego prawym dziecku

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

1. AWstawianie elementów na dowolnej pozycji
2. BZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
3. CSortowanie tablicy i wyszukiwanie binarne
4. DZnajdowanie mediany w O(1)

Algorytm Kahna sortowania topologicznego wielokrotnie usuwa wierzchołki o stopniu wejściowym 0. Która struktura przechowuje te wierzchołki?

1. AStos wszystkich odwiedzonych krawędzi
2. BKopiec maksymalny uporządkowany według stopnia wyjściowego
3. CKolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0
4. DMacierz sąsiedztwa zapisującą, które wierzchołki zostały już usunięte