Struktury danych: karta pracy z odpowiedziami

Czym jest kolizja w tablicy mieszającej?

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

W jakiej kolejności przejście preorder (wzdłużne) drzewa binarnego odwiedza węzły?

1. ALewe poddrzewo, potem węzeł, potem prawe poddrzewo
2. BPoziomami, od góry
3. CWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
4. DLewe poddrzewo, potem prawe poddrzewo, potem węzeł

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

1. AKolejka
2. BStos
3. CLista wiązana
4. DTablica mieszająca

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

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

Ile węzłów ma doskonałe drzewo binarne o wysokości h, gdy wysokość liczy się w krawędziach?

1. A2^h
2. B2^h+1 − 1
3. C2h + 1
4. Dh²

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

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

Która para przejść zawsze jednoznacznie wyznacza drzewo binarne o różnych kluczach?

1. APreorder i postorder
2. BSam preorder
3. CPreorder i inorder
4. DSamo przejście poziomami

Jaką gwarancję co do wysokości drzewa z n kluczami dają reguły drzewa czerwono-czarnego?

1. AWysokość wynosi co najwyżej n / 2
2. BWysokość wynosi dokładnie log₂ n
3. CWysokość wynosi co najwyżej log₂ n + 1
4. DWysokość wynosi co najwyżej 2 log₂(n + 1)