Struktury danych: karta pracy z odpowiedziami

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

1. AKolejka
2. BStos
3. CLista wiązana
4. DTablica mieszająca

Co zawiera wskaźnik next ostatniego węzła listy jednokierunkowej?

1. AAdres pierwszego węzła
2. BAdres poprzedniego węzła
3. CLiczbę węzłów na liście
4. DNull (brak węzła)

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

1. ADrzewo binarne
2. BKopiec
3. CKolejka
4. DStos

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

1. AKażdy wiersz ma dokładnie jedną jedynkę
2. BJest symetryczna względem głównej przekątnej
3. CNa jej głównej przekątnej zawsze są jedynki
4. DJest zawsze górnotrójkątna

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

1. AIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
2. BIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
3. COdwiedzić każdy liść i porównać je
4. DSprawdzić tylko korzeń

Dlaczego przechodzenie tablicy jest w praktyce często znacznie szybsze niż przechodzenie listy wiązanej o tej samej długości?

1. ATablice wymagają mniej instrukcji do porównania wartości
2. BPrzejście tablicy ma łącznie złożoność O(1), a listy wiązanej O(n)
3. CElementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora
4. DListy wiązane zawsze przechowują elementy na dysku

Która struktura pozwala obliczyć maksimum każdego okna o rozmiarze k w tablicy w łącznym czasie O(n)?

1. ADeque przechowująca indeksy w kolejności malejących wartości
2. BPosortowana tablica aktualizowana przez przesuwanie
3. CLista jednokierunkowa elementów okna
4. DKopiec minimalny budowany od nowa dla każdego okna

Która własność sprawia, że każde B-drzewo jest idealnie zrównoważone?

1. AKażdy węzeł przechowuje jeden klucz
2. BWszystkie liście są na tej samej głębokości
3. CKażdy węzeł ma dokładnie dwoje dzieci
4. DKlucze są przechowywane tylko w korzeniu