Struktury danych: karta pracy z odpowiedziami

Czym jest deque (kolejka dwustronna)?

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

Czym jest kolizja w tablicy mieszającej?

1. AWyczerpaniem pamięci przez tablicę
2. BDwukrotnym zapisaniem dwóch równych kluczy
3. COdwzorowaniem dwóch różnych kluczy na ten sam indeks
4. DSytuacją, w której klucza w ogóle nie da się zahaszować

Która operacja jest wolna w tablicy, ale szybka na początku listy wiązanej?

1. AWstawianie na początku
2. BUstalenie długości tablicy o stałym rozmiarze
3. COdczyt ostatniego elementu po indeksie
4. DDostęp do 5. elementu

Jaki warunek zrównoważenia utrzymuje drzewo AVL w każdym węźle?

1. AKażdy węzeł jest pokolorowany na czerwono lub czarno
2. BOba poddrzewa każdego węzła zawierają dokładnie tyle samo węzłów
3. CWysokości lewego i prawego poddrzewa różnią się co najwyżej o 1
4. DWszystkie liście są na dokładnie tej samej głębokości

Dlaczego przechodzenie tablicy jest w praktyce często znacznie szybsze niż przechodzenie listy wiązanej o tej samej długości?

1. APrzejście tablicy ma łącznie złożoność O(1), a listy wiązanej O(n)
2. BListy wiązane zawsze przechowują elementy na dysku
3. CTablice wymagają mniej instrukcji do porównania wartości
4. DElementy tablicy leżą obok siebie, więc dobrze wykorzystują pamięć podręczną procesora

Ile trwa wyszukiwanie słowa o długości L w drzewie trie ze stałym alfabetem?

1. AO(L × n)
2. BO(n), gdzie n to liczba słów
3. CO(log n), gdzie n to liczba słów
4. DO(L), niezależnie od liczby przechowywanych słów

Złożoność czasowa operacji decrease-key w kopcu binarnym (przy znanej pozycji elementu) wynosi:

1. AO(log n)
2. BO(1)
3. CO(n log n)
4. DO(n)

Algorytm Kahna sortowania topologicznego wielokrotnie usuwa wierzchołki o stopniu wejściowym 0. Która struktura przechowuje te wierzchołki?

1. AKopiec maksymalny uporządkowany według stopnia wyjściowego
2. BMacierz sąsiedztwa zapisującą, które wierzchołki zostały już usunięte
3. CStos wszystkich odwiedzonych krawędzi
4. DKolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0