Struktury danych: karta pracy z odpowiedziami

Której struktury danych używa się do przejścia drzewa poziomami (level-order)?

1. AKolejki
2. BTablicy mieszającej
3. CKolejki priorytetowej
4. DStosu

Która struktura danych najlepiej nadaje się do funkcji „cofnij” (undo) w edytorze tekstu?

1. AGraf
2. BZbiór mieszający
3. CStos
4. DKolejka

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

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

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 postorder?

1. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D4 2 5 1 3

Dlaczego przechodzenie tablicy jest w praktyce często znacznie szybsze niż przechodzenie listy wiązanej o tej samej długości?

1. AListy wiązane zawsze przechowują elementy na dysku
2. BTablice wymagają mniej instrukcji do porównania wartości
3. CPrzejście tablicy ma łącznie złożoność O(1), a listy wiązanej O(n)
4. DElementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora

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. CZawsze w jego prawym dziecku
4. DW skrajnie prawym węźle jego lewego poddrzewa

Która własność sprawia, że każde B-drzewo jest idealnie zrównoważone?

1. AKażdy węzeł przechowuje jeden klucz
2. BKażdy węzeł ma dokładnie dwoje dzieci
3. CWszystkie liście są na tej samej głębokości
4. DKlucze są przechowywane tylko w korzeniu

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

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