Struktury danych: karta pracy z odpowiedziami

Czym jest deque (kolejka dwustronna)?

1. AStrukturą pozwalającą wstawiać i usuwać elementy na obu końcach
2. BDwiema oddzielnymi kolejkami dzielącymi jedną tablicę
3. CKolejką posortowaną według priorytetu
4. DKolejką, która pozwala usuwać elementy tylko z końca

Co zawiera każdy węzeł listy dwukierunkowej?

1. ADane i dwa wskaźniki: jeden do następnego węzła i jeden do węzła po nim
2. BDane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
3. CDane i tylko wskaźnik na następny węzeł
4. DDwie kopie danych i jeden wskaźnik

Jaka jest główna różnica między tablicą statyczną a tablicą dynamiczną?

1. ATablica statyczna ma wolniejszy dostęp po indeksie
2. BTablica dynamiczna przechowuje elementy w połączonych węzłach, by mogła rosnąć po jednym elemencie
3. CTablica statyczna może przechowywać tylko liczby
4. DTablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci

Dlaczego kopiec binarny można przechowywać w tablicy bez żadnych wskaźników?

1. ATablice automatycznie utrzymują klucze w kolejności posortowanej, więc wskaźniki nie są potrzebne
2. BKopce nigdy nie zawierają więcej niż 100 elementów
3. CWszystkie klucze w kopcu są równe
4. DJest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy

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

1. A0,5
2. B2
3. C1
4. DNie ma maksimum

Bufor cykliczny (ring buffer) jest powszechnie używany do implementacji:

1. AFunkcji mieszającej
2. BPrzechodzenia grafu
3. CKolejki o stałym rozmiarze
4. DBinarnego drzewa poszukiwań

Jaki jest koszt czasowy i dodatkowy pamięciowy odwrócenia listy jednokierunkowej w miejscu?

1. ACzas O(n) i dodatkowa pamięć O(n)
2. BCzas O(n) i dodatkowa pamięć O(1)
3. CCzas O(n log n) i dodatkowa pamięć O(1)
4. DCzas O(1) i dodatkowa pamięć O(1)

Struktura union-find (zbiory rozłączne) z łączeniem według rangi i kompresją ścieżki ma zamortyzowany koszt operacji równy:

1. ADokładnie O(log n)
2. BO(n²)
3. CO(n)
4. DO(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała