Struktury danych: karta pracy z odpowiedziami

Czym jest korzeń drzewa?

1. AWęzeł bez dzieci
2. BDowolny węzeł w środku
3. CWęzeł o największej wartości
4. DNajwyższy węzeł, który nie ma rodzica

Która struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

1. AKolejka
2. BStos
3. CTablica mieszająca
4. DLista wiązana

Która struktura danych działa według zasady „pierwszy na wejściu, pierwszy na wyjściu” (FIFO)?

1. AStos
2. BKopiec
3. CKolejka
4. DDrzewo binarne

Której struktury danych używa przeszukiwanie w głąb (DFS) w wersji iteracyjnej?

1. AWyłącznie tablicy mieszającej
2. BKopca
3. CStosu
4. DKolejki

Jak działa extract-min w binarnym kopcu minimalnym?

1. APrzenosi się ostatni element do korzenia i przesuwa go w dół
2. BPrzeszukuje się wszystkie liście w poszukiwaniu nowego minimum
3. CUsuwa się korzeń i przesuwa wszystkie elementy o jedno miejsce w lewo
4. DUsuwa się ostatni element tablicy

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

1. AJest symetryczna względem głównej przekątnej
2. BNa jej głównej przekątnej zawsze są jedynki
3. CKażdy wiersz ma dokładnie jedną jedynkę
4. DJest zawsze górnotrójkątna

W buforze cyklicznym front == rear może oznaczać bufor pusty albo pełny. Jaki jest popularny sposób ich rozróżnienia?

1. AUstawienie rozmiaru bufora na potęgę dwójki
2. BCzyszczenie bufora za każdym razem, gdy front równa się rear, więc stan jest pusty
3. CPrzechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
4. DPrzechowywanie front i rear w tej samej zmiennej

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

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