Struktury danych: karta pracy z odpowiedziami

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

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

Czym jest cykl w grafie?

1. AWierzchołkiem bez krawędzi
2. BŚcieżką, która odwiedza każdy wierzchołek
3. CKrawędzią o wadze zero
4. DŚcieżką, która zaczyna się i kończy w tym samym wierzchołku

Czym jest deque (kolejka dwustronna)?

1. AKolejką posortowaną według priorytetu
2. BDwiema oddzielnymi kolejkami dzielącymi jedną tablicę
3. CKolejką, która pozwala usuwać elementy tylko z końca
4. DStrukturą pozwalającą wstawiać i usuwać elementy na obu końcach

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

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

Którego abstrakcyjnego typu danych używa algorytm Dijkstry do wyboru następnego wierzchołka do przetworzenia?

1. AKolejki FIFO
2. BKolejki priorytetowej typu min
3. CStosu
4. DZbioru bez uporządkowania

Jak wstawia się nowy element do kopca binarnego?

1. AWstawia się go na właściwą posortowaną pozycję, przesuwając o jedno miejsce w prawo wszystkie większe elementy
2. BBuduje się cały kopiec od nowa
3. CUmieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
4. DUmieszcza się go w korzeniu i przesuwa w dół

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. BZnajdowanie mediany w O(1)
3. CZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
4. DWstawianie elementów na dowolnej pozycji

Do czego służy struktura union-find w algorytmie Kruskala wyznaczania minimalnego drzewa rozpinającego?

1. ADo wyboru wierzchołka początkowego
2. BDo przechowywania bieżącej odległości każdego wierzchołka od źródła w trakcie przeszukiwania
3. CDo sortowania krawędzi według wag
4. DDo sprawdzania, czy oba końce krawędzi są już połączone