Struktury danych: karta pracy z odpowiedziami

Jak nazywa się operacja na kolejce, która usuwa element z jej początku?

1. APush
2. BEnqueue
3. CInsert
4. DDequeue

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

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

Graf składa się z:

1. ATylko korzenia i liści
2. BWierszy i kolumn
3. CWierzchołków (węzłów) połączonych krawędziami
4. DWyłącznie kluczy i skrótów

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

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

Tablica mieszająca o rozmiarze 7 używa h(k) = k mod 7 i próbkowania liniowego. Gdzie zostanie zapisane 17 po wstawieniu 10?

1. APod indeksem 3
2. BPod indeksem 6
3. CPod indeksem 4
4. DPod indeksem 0

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

Jaką gwarancję co do wysokości drzewa z n kluczami dają reguły drzewa czerwono-czarnego?

1. AWysokość wynosi co najwyżej log₂ n + 1
2. BWysokość wynosi co najwyżej 2 log₂(n + 1)
3. CWysokość wynosi dokładnie log₂ n
4. DWysokość wynosi co najwyżej n / 2

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

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