Struktury danych: karta pracy z odpowiedziami

Jak elementy tablicy są przechowywane w pamięci?

1. AW losowych miejscach wybranych przez funkcję mieszającą
2. BW drzewie stron pamięci
3. CW rozproszeniu, połączone wskaźnikami
4. DW jednym ciągłym bloku, jeden po drugim

Co zawiera każdy węzeł listy dwukierunkowej?

1. ADwie kopie danych i jeden wskaźnik
2. BDane i tylko wskaźnik na następny węzeł
3. CDane, wskaźnik na następny węzeł i wskaźnik na poprzedni węzeł
4. DDane i dwa wskaźniki: jeden do następnego węzła i jeden do węzła po nim

Czym jest graf ważony?

1. AGrafem przechowywanym na dysku
2. BGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
3. CGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
4. DGrafem, który ma więcej krawędzi niż wierzchołków

Aplikacja potrzebuje szybkiego wyszukiwania, a także wypisywania kluczy w kolejności posortowanej i odpowiadania na zapytania o zakres. Która struktura pasuje najlepiej?

1. ANieposortowana lista wiązana
2. BTablica mieszająca
3. CStos
4. DZrównoważone binarne drzewo poszukiwań

Ile czasu zajmuje sprawdzenie, czy istnieje krawędź (u, v), przy użyciu macierzy sąsiedztwa?

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

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 0
3. CPod indeksem 6
4. DPod indeksem 4

Czym drzewo radix (skompresowane trie) przewyższa zwykłe trie?

1. AŁączy łańcuchy węzłów z jednym dzieckiem w jedną krawędź etykietowaną ciągiem znaków
2. BPrzechowuje każde słowo w tablicy mieszającej w korzeniu zamiast w osobnych węzłach
3. CSortuje dzieci każdego węzła według częstości
4. DZachowuje tylko pierwszą literę każdego słowa

Która własność sprawia, że każde B-drzewo jest idealnie zrównoważone?

1. AKażdy węzeł ma dokładnie dwoje dzieci
2. BKażdy węzeł przechowuje jeden klucz
3. CWszystkie liście są na tej samej głębokości
4. DKlucze są przechowywane tylko w korzeniu