Struktury danych: karta pracy z odpowiedziami

Czym jest liść w drzewie?

1. AWęzłem bez rodzica
2. BWęzłem bez dzieci
3. CWęzłem z dokładnie jednym dzieckiem
4. DWęzłem o największej wartości

Która struktura jest zwykle używana do implementacji kolejki priorytetowej?

1. AStos
2. BCiąg znaków
3. CKopiec
4. DNieuporządkowana lista jednokierunkowa

Która struktura danych najlepiej nadaje się do funkcji „cofnij” (undo) w edytorze tekstu?

1. AGraf
2. BStos
3. CKolejka
4. DZbiór mieszający

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. BTablice wymagają mniej instrukcji do porównania wartości
3. CListy wiązane zawsze przechowują elementy na dysku
4. DPrzejście tablicy ma łącznie złożoność O(1), a listy wiązanej O(n)

Drzewo trie (drzewo prefiksowe) jest szczególnie wydajne przy:

1. APrzechowywaniu macierzy
2. BWyszukiwaniu po prefiksie, np. autouzupełnianiu
3. CZnajdowaniu najkrótszych ścieżek
4. DSortowaniu liczb

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

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

1. ASortowanie tablicy i wyszukiwanie binarne
2. BZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
3. CWstawianie elementów na dowolnej pozycji
4. DZnajdowanie mediany w O(1)

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

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