Struktury danych: karta pracy z odpowiedziami

Czym jest deque (kolejka dwustronna)?

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

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

1. ASzyfruje wartości w tablicy
2. BSortuje klucze w tablicy
3. COdwzorowuje klucz na indeks w tablicy
4. DLiczy, ile kluczy jest przechowywanych

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

1. AGraf
2. BStos
3. CKolejka
4. DZbiór mieszający

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

1. Ai + 1 i i + 2
2. B2i i 2i + 1
3. Ci/2 i i/2 + 1
4. D2i + 1 i 2i + 2

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. ATablica mieszająca
2. BStos
3. CNieposortowana lista wiązana
4. DZrównoważone binarne drzewo poszukiwań

Jak znaleźć najmniejszy klucz w binarnym drzewie poszukiwań?

1. AOdwiedzić każdy liść i porównać je
2. BIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
3. CSprawdzić tylko korzeń
4. DIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka

Która struktura pozwala obliczyć maksimum każdego okna o rozmiarze k w tablicy w łącznym czasie O(n)?

1. APosortowana tablica aktualizowana przez przesuwanie
2. BDeque przechowująca indeksy w kolejności malejących wartości
3. CKopiec minimalny budowany od nowa dla każdego okna
4. DLista jednokierunkowa elementów okna

Dlaczego w tablicy mieszającej z adresowaniem otwartym usuwanie wykonuje się często za pomocą znacznika „nagrobka” (tombstone)?

1. AUsunięte klucze muszą być przechowywane na zawsze ze względów bezpieczeństwa, więc miejsc nigdy nie można użyć ponownie
2. BDzięki temu tablica staje się posortowana
3. CNagrobki przyspieszają haszowanie
4. DOpróżnienie miejsca mogłoby przerwać sekwencję sondowania dla innych kluczy