Struktury danych: karta pracy z odpowiedziami

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

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

Co definiuje drzewo binarne?

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

Czym jest cykl w grafie?

1. AKrawędzią o wadze zero
2. BŚcieżką, która zaczyna się i kończy w tym samym wierzchołku
3. CŚcieżką, która odwiedza każdy wierzchołek
4. DWierzchołkiem bez krawędzi

Jaki jest maksymalny możliwy współczynnik zapełnienia tablicy mieszającej z adresowaniem otwartym?

1. A1
2. B0,5
3. C2
4. DNie ma maksimum

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. B2h + 1
3. C2^h
4. Dh²

Która metoda rozwiązywania kolizji przechowuje kolidujące klucze w liście w tym samym kubełku?

1. AŁańcuchowanie (separate chaining)
2. BSondowanie kwadratowe
3. CHaszowanie podwójne
4. DSondowanie liniowe

Jaki jest oczekiwany czas wyszukiwania przy prostym równomiernym haszowaniu w tablicy mieszającej z metodą łańcuchową, n kluczami i m kubełkami?

1. AO(1 + α), gdzie α = n / m
2. BO(log n)
3. CO(n)
4. DO(m)

Wstawienie klucza do drzewa AVL sprawia, że lewe poddrzewo pewnego węzła staje się zbyt wysokie, a nowy klucz trafił do lewego poddrzewa jego lewego dziecka (przypadek lewo-lewo). Jaką naprawę się stosuje?

1. APrzekolorowanie węzła i jego dziecka
2. BPojedynczą rotację w prawo w niezrównoważonym węźle
3. CRotację w lewo w dziecku, a potem rotację w prawo w węźle
4. DPojedynczą rotację w lewo w niezrównoważonym węźle