Struktury danych: karta pracy z odpowiedziami

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

1. ATablicy mieszającej
2. BKolejki priorytetowej
3. CKolejki
4. DStosu

W binarnym drzewie poszukiwań wartości w lewym poddrzewie węzła są:

1. AMniejsze od wartości węzła
2. BW losowej kolejności
3. CWiększe od wartości węzła
4. DRówne wartości węzła

Czym jest kolizja w tablicy mieszającej?

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

Którego abstrakcyjnego typu danych używa algorytm Dijkstry do wyboru następnego wierzchołka do przetworzenia?

1. AKolejki FIFO
2. BZbioru bez uporządkowania
3. CStosu
4. DKolejki priorytetowej typu min

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

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

Jak znaleźć najmniejszy klucz w binarnym drzewie poszukiwań?

1. AOdwiedzić każdy liść i porównać je
2. BSprawdzić tylko korzeń
3. CIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
4. DIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka

Dla każdego elementu tablicy chcesz znaleźć najbliższy większy element po jego prawej stronie, w łącznym czasie O(n). Która struktura pomaga?

1. ATablica mieszająca wszystkich elementów
2. BBinarne drzewo poszukiwań budowane od nowa dla każdego elementu
3. CKolejka przechowująca każdą parę elementów
4. DStos przechowujący elementy czekające na swoją odpowiedź

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

1. AZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
2. BZamianę go z korzeniem
3. CUsunięcie całego poddrzewa
4. DZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy