Struktury danych: karta pracy z odpowiedziami

Co robi funkcja mieszająca w tablicy mieszającej?

1. ASzyfruje wartości w tablicy
2. BLiczy, ile kluczy jest przechowywanych
3. CSortuje klucze w tablicy
4. DOdwzorowuje klucz na indeks w tablicy

Której struktury danych używa się do przejścia drzewa poziomami (level-order)?

1. ATablicy mieszającej
2. BKolejki
3. CKolejki priorytetowej
4. DStosu

Która struktura danych najlepiej nadaje się do funkcji „cofnij” (undo) w edytorze tekstu?

1. AZbiór mieszający
2. BGraf
3. CKolejka
4. DStos

Jaki jest maksymalny możliwy współczynnik zapełnienia tablicy mieszającej z adresowaniem otwartym?

1. A1
2. B0,5
3. CNie ma maksimum
4. D2

W binarnym kopcu minimalnym przechowywanym w tablicy (indeksowanie od 0) dzieci węzła o indeksie i znajdują się na pozycjach:

1. Ai/2 i i/2 + 1
2. B2i + 1 i 2i + 2
3. C2i i 2i + 1
4. Di + 1 i i + 2

Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?

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

Jaki jest koszt czasowy i dodatkowy pamięciowy odwrócenia listy jednokierunkowej w miejscu?

1. ACzas O(n) i dodatkowa pamięć O(1)
2. BCzas O(n) i dodatkowa pamięć O(n)
3. CCzas O(1) i dodatkowa pamięć O(1)
4. DCzas O(n log n) i dodatkowa pamięć O(1)

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

1. ALiczyć węzły, aż liczba przekroczy pole z długością listy
2. BZapisywać każdy odwiedzony węzeł w zbiorze mieszającym
3. CPosortować listę i szukać duplikatów
4. DPrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają