Struktury danych: karta pracy z odpowiedziami

Co robi operacja peek (lub top) na stosie?

1. AZwraca element z dna stosu
2. BUsuwa element z wierzchołka i go zwraca
3. CUsuwa wszystkie elementy ze stosu
4. DZwraca element z wierzchołka bez usuwania go

Której struktury danych używa się do przejścia drzewa poziomami (level-order)?

1. AStosu
2. BKolejki priorytetowej
3. CKolejki
4. DTablicy mieszającej

Co przechowuje mapa (słownik)?

1. AWartości posortowane według wielkości
2. BPary równych kluczy
3. CTylko wartości w kolejności wstawiania
4. DPary klucz–wartość z unikalnymi kluczami

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

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

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

1. AO(log n), z powodu wyszukiwania binarnego
2. BO(n²), bo każdy element przesuwa się n razy
3. CO(n), bo dalsze elementy trzeba przesunąć
4. DO(1), bo indeks jest znany

Drzewa AVL i drzewa czerwono-czarne gwarantują:

1. APrzechowywanie kluczy w kolejności wstawiania
2. BWyszukiwanie w czasie stałym w każdym przypadku
3. CŻe żaden węzeł nie ma dwojga dzieci
4. DWysokość O(log n) dzięki równoważeniu

Co robi drzewo splay po każdym dostępie?

1. APrzenosi odwiedzony węzeł do liścia
2. BPrzekolorowuje węzły na ścieżce wyszukiwania
3. CRotacjami przenosi odwiedzony węzeł do korzenia
4. DBuduje całe drzewo od nowa w formie zrównoważonej

Który problem próbkowania liniowego zmniejsza przede wszystkim haszowanie podwójne?

1. AGrupowanie pierwotne (primary clustering), czyli powstawanie długich ciągów zajętych pozycji
2. BKoszt O(n) odczytu wartości klucza
3. CPotrzebę przechowywania kluczy w tablicy
4. DPotrzebę funkcji mieszającej