Struktury danych: karta pracy z odpowiedziami

Tablica mieszająca (hash table) przechowuje dane jako:

1. ADrzewo z uporządkowanymi kluczami
2. BPary klucz–wartość lokalizowane przez funkcję mieszającą
3. CCiąg znaków o stałej długości
4. DWyłącznie posortowaną listę

Co definiuje drzewo binarne?

1. ADrzewo ma dokładnie dwa poziomy
2. BKażdy węzeł ma co najwyżej dwoje dzieci
3. CKażdy węzeł ma dokładnie dwoje dzieci
4. DKażdy węzeł przechowuje liczbę binarną

Co przechowuje mapa (słownik)?

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

Której struktury danych używa się, by sprawdzić, czy nawiasy w „{[()]}” są zrównoważone?

1. AStosu
2. BKolejki
3. CBinarnego drzewa poszukiwań
4. DTablicy mieszającej

W binarnym kopcu minimalnym przechowywanym w tablicy (indeksowanie od 0) dzieci węzła o indeksie i znajdują się na pozycjach:

1. Ai/2 i i/2 + 1
2. B2i i 2i + 1
3. Ci + 1 i i + 2
4. D2i + 1 i 2i + 2

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(n)
2. BO(log n)
3. CO(n²)
4. DO(1)

Dlaczego serwer może losowo wybierać funkcję mieszającą z rodziny uniwersalnej?

1. ABy zagwarantować, że żadne dwa klucze nigdy nie będą kolidować, jakie klucze by nie wysłał atakujący
2. BBy wyeliminować potrzebę zmiany rozmiaru tablicy
3. CBy było bardzo mało prawdopodobne, że atakujący dobierze wiele kluczy, które wszystkie kolidują
4. DBy tablica mieszająca była posortowana

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

1. APrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
2. BZapisywać każdy odwiedzony węzeł w zbiorze mieszającym
3. CPosortować listę i szukać duplikatów
4. DLiczyć węzły, aż liczba przekroczy pole z długością listy