Struktury danych: karta pracy z odpowiedziami

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

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

Czym jest współczynnik zapełnienia (load factor) tablicy mieszającej?

1. ADotychczasową liczbą kolizji
2. BLiczbą kubełków podzieloną przez średnią długość przechowywanych kluczy
3. CCzasem potrzebnym do wczytania tablicy z dysku
4. DLiczbą przechowywanych elementów podzieloną przez liczbę kubełków

Co definiuje drzewo binarne?

1. AKażdy węzeł ma co najwyżej dwoje dzieci
2. BKażdy węzeł przechowuje liczbę binarną
3. CDrzewo ma dokładnie dwa poziomy
4. DKażdy węzeł ma dokładnie dwoje dzieci

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

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

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

1. AO(n), bo dalsze elementy trzeba przesunąć
2. BO(1), bo indeks jest znany
3. CO(n²), bo każdy element przesuwa się n razy
4. DO(log n), z powodu wyszukiwania binarnego

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

1. ARosnącej (posortowanej)
2. BPoziomami
3. CWstawiania
4. DZawsze malejącej

W buforze cyklicznym front == rear może oznaczać bufor pusty albo pełny. Jaki jest popularny sposób ich rozróżnienia?

1. APrzechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
2. BPrzechowywanie front i rear w tej samej zmiennej
3. CCzyszczenie bufora za każdym razem, gdy front równa się rear, więc stan jest pusty
4. DUstawienie rozmiaru bufora na potęgę dwójki

Do czego służy struktura union-find w algorytmie Kruskala wyznaczania minimalnego drzewa rozpinającego?

1. ADo sortowania krawędzi według wag
2. BDo przechowywania bieżącej odległości każdego wierzchołka od źródła w trakcie przeszukiwania
3. CDo sprawdzania, czy oba końce krawędzi są już połączone
4. DDo wyboru wierzchołka początkowego