Struktury danych: karta pracy z odpowiedziami

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

1. AStos
2. BKopiec
3. CKolejka
4. DDrzewo binarne

Czym jest współczynnik zapełnienia (load factor) tablicy mieszającej?

1. ALiczbą kubełków podzieloną przez średnią długość przechowywanych kluczy
2. BDotychczasową liczbą kolizji
3. CLiczbą przechowywanych elementów podzieloną przez liczbę kubełków
4. DCzasem potrzebnym do wczytania tablicy z dysku

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

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

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

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

Drzewo binarne ma korzeń 1 z lewym dzieckiem 2 i prawym dzieckiem 3; węzeł 2 ma dzieci 4 (lewe) i 5 (prawe). Jaki jest wynik przejścia postorder?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D5 4 3 2 1

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

1. AZnajdowaniu najkrótszych ścieżek
2. BWyszukiwaniu po prefiksie, np. autouzupełnianiu
3. CSortowaniu liczb
4. DPrzechowywaniu macierzy

Jaki jest oczekiwany czas wyszukiwania przy prostym równomiernym haszowaniu w tablicy mieszającej z metodą łańcuchową, n kluczami i m kubełkami?

1. AO(log n)
2. BO(m)
3. CO(1 + α), gdzie α = n / m
4. DO(n)

Obiekt jest przechowywany jako klucz w mapie mieszającej, a następnie zmienia się pole używane przez jego funkcję mieszającą. Jaki jest prawdopodobny skutek?

1. AMapa zgłasza błąd w chwili zmiany pola
2. BNic się nie zmienia, bo skrót klucza oblicza się tylko raz przy uruchomieniu programu
3. CWyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu
4. DMapa automatycznie przenosi klucz do nowego kubełka