Struktury danych: karta pracy z odpowiedziami

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

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

Która struktura danych działa według zasady „pierwszy na wejściu, pierwszy na wyjściu” (FIFO)?

1. AKopiec
2. BKolejka
3. CDrzewo binarne
4. DStos

W liście jednokierunkowej każdy węzeł zawiera:

1. ADane i indeks
2. BDane i referencje do wszystkich pozostałych węzłów
3. CTylko dane
4. DDane i referencję do następnego węzła

Której struktury danych używa się, by sprawdzić, czy nawiasy w „{[()]}” są zrównoważone?

1. ABinarnego drzewa poszukiwań
2. BStosu
3. CTablicy mieszającej
4. DKolejki

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. BIstniejące klucze są sortowane w miejscu
3. CAlokuje się większą tablicę i ponownie wstawia każdy klucz
4. DNajstarsze klucze są usuwane, by zrobić miejsce

Ile czasu zajmuje sprawdzenie, czy istnieje krawędź (u, v), przy użyciu macierzy sąsiedztwa?

1. AO(E)
2. BO(log V)
3. CO(V)
4. DO(1)

Tablica dynamiczna podwaja rozmiar, gdy jest pełna. Dlaczego wiele implementacji zmniejsza ją dopiero przy zapełnieniu w jednej czwartej, a nie w połowie?

1. ABo alokator pamięci może zwalniać pamięć tylko w ćwiartkach bloku
2. BBy uniknąć wielokrotnej zmiany rozmiaru, gdy operacje push i pop przeplatają się w pobliżu granicy
3. CBo zmniejszanie o połowę przy zapełnieniu w połowie spowodowałoby utratę elementów
4. DBy utrzymać tablicę posortowaną

Dlaczego B-drzewa są używane w bazach danych i systemach plików?

1. APrzechowują dane nieposortowane
2. BNie wymagają równoważenia
3. CZajmują mniej pamięci niż jakakolwiek tablica, więc cały indeks zawsze mieści się w pamięci głównej
4. DDuży stopień rozgałęzienia utrzymuje drzewo płytkim, ograniczając wolne odczyty z dysku