Struktury danych: karta pracy z odpowiedziami

Która operacja ma złożoność O(1) dla tablicy, ale O(n) dla listy jednokierunkowej?

1. AOdczyt pierwszego elementu
2. BDostęp do elementu o indeksie i
3. CUsuwanie pierwszego elementu
4. DWstawianie na początku

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

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

Wysokość drzewa definiuje się zwykle jako:

1. ALiczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
2. BLiczbę liści w drzewie
3. CLiczbę dzieci korzenia
4. DŁączną liczbę węzłów w drzewie, wliczając korzeń i każdy liść

Kolejkę zaimplementowano za pomocą dwóch stosów: push na stos „in”, a pop ze stosu „out”, który, gdy jest pusty, uzupełnia się ze stosu „in”. Jaki jest zamortyzowany koszt jednej operacji?

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

Przejście in-order (poprzeczne) binarnego drzewa poszukiwań odwiedza klucze w kolejności:

1. AWstawiania
2. BZawsze malejącej
3. CRosnącej (posortowanej)
4. DPoziomami

Jaka jest wartość wyrażenia w notacji postfiksowej 3 4 + 2 * ?

1. A10
2. B14
3. C11
4. D24

Obiekt jest przechowywany jako klucz w mapie mieszającej, a następnie zmienia się pole używane przez jego funkcję mieszającą. Jaki jest prawdopodobny skutek?

1. AMapa zgłasza błąd w chwili zmiany pola
2. BNic się nie zmienia, bo skrót klucza oblicza się tylko raz przy uruchomieniu programu
3. CWyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu
4. DMapa automatycznie przenosi klucz do nowego kubełka

Która para przejść zawsze jednoznacznie wyznacza drzewo binarne o różnych kluczach?

1. ASamo przejście poziomami
2. BSam preorder
3. CPreorder i inorder
4. DPreorder i postorder