Struktury danych: karta pracy z odpowiedziami

Czym jest cykl w grafie?

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

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

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

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

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

Sieć drogowa ma 100 000 skrzyżowań, z których każde łączy się z około 4 innymi. Która reprezentacja jest najodpowiedniejsza?

1. AKopiec binarny krawędzi
2. BMacierz sąsiedztwa
3. CJedna posortowana tablica wierzchołków
4. DListy sąsiedztwa

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

Jak wstawia się nowy element do kopca binarnego?

1. AUmieszcza się go w korzeniu i przesuwa w dół
2. BUmieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
3. CWstawia się go na właściwą posortowaną pozycję, przesuwając o jedno miejsce w prawo wszystkie większe elementy
4. DBuduje się cały kopiec od nowa

Jaki jest pesymistyczny koszt pojedynczej operacji find w strukturze union-find z n elementami bez łączenia według rangi (union by rank) i bez kompresji ścieżek?

1. AO(n)
2. BO(1)
3. CO(α(n))
4. DO(log n)

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 zmniejszanie o połowę przy zapełnieniu w połowie spowodowałoby utratę elementów
2. BBy utrzymać tablicę posortowaną
3. CBy uniknąć wielokrotnej zmiany rozmiaru, gdy operacje push i pop przeplatają się w pobliżu granicy
4. DBo alokator pamięci może zwalniać pamięć tylko w ćwiartkach bloku