Struktury danych: karta pracy z odpowiedziami

Głębokość węzła w drzewie to:

1. ALiczba krawędzi od korzenia do tego węzła
2. BLiczba krawędzi od tego węzła do najgłębszego liścia
3. CLiczba dzieci tego węzła
4. DLiczba węzłów w jego poddrzewie

Czym jest graf ważony?

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

Która operacja jest wolna w tablicy, ale szybka na początku listy wiązanej?

1. AUstalenie długości tablicy o stałym rozmiarze
2. BWstawianie na początku
3. COdczyt ostatniego elementu po indeksie
4. DDostęp do 5. elementu

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

1. AJest zawsze górnotrójkątna
2. BKażdy wiersz ma dokładnie jedną jedynkę
3. CNa jej głównej przekątnej zawsze są jedynki
4. DJest symetryczna względem głównej przekątnej

Ile węzłów ma doskonałe drzewo binarne o wysokości h, gdy wysokość liczy się w krawędziach?

1. A2^h+1 − 1
2. B2^h
3. Ch²
4. D2h + 1

Ile pamięci zajmują listy sąsiedztwa dla grafu o V wierzchołkach i E krawędziach?

1. AO(V²)
2. BO(V + E)
3. CO(E²)
4. DO(V × E)

Węzeł AVL jest niezrównoważony, bo prawe poddrzewo jego lewego dziecka stało się zbyt wysokie (przypadek lewo-prawo). Jaką naprawę się stosuje?

1. APojedynczą rotację w lewo w węźle
2. BPojedynczą rotację w prawo w węźle
3. CRotację w lewo w lewym dziecku, a potem rotację w prawo w węźle
4. DRotację w prawo w lewym dziecku, a potem rotację w lewo w węźle

Co robi drzewo splay po każdym dostępie?

1. ARotacjami przenosi odwiedzony węzeł do korzenia
2. BPrzekolorowuje węzły na ścieżce wyszukiwania
3. CPrzenosi odwiedzony węzeł do liścia
4. DBuduje całe drzewo od nowa w formie zrównoważonej