Struktury danych: karta pracy z odpowiedziami

Ile krawędzi ma drzewo o n węzłach?

1. A2n
2. Bn
3. Cn − 1
4. Dn + 1

Co przechowuje się dla każdego wierzchołka w reprezentacji grafu za pomocą list sąsiedztwa?

1. AWiersz V wartości logicznych
2. BNajkrótszą ścieżkę do każdego innego wierzchołka
3. CListę jego sąsiednich wierzchołków
4. DŁączną liczbę krawędzi w grafie

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

1. ADrzewo binarne
2. BKolejka
3. CKopiec
4. DStos

Której struktury danych używa przeszukiwanie w głąb (DFS) w wersji iteracyjnej?

1. AStosu
2. BWyłącznie tablicy mieszającej
3. CKolejki
4. DKopca

Co się dzieje, gdy tablica mieszająca wykonuje rehashing po przekroczeniu progu współczynnika zapełnienia?

1. ATylko kolidujące klucze są przenoszone na nową listę nadmiarową na końcu tablicy
2. BIstniejące klucze są sortowane w miejscu
3. CNajstarsze klucze są usuwane, by zrobić miejsce
4. DAlokuje się większą tablicę i ponownie wstawia każdy klucz

Ile pamięci zajmuje macierz sąsiedztwa grafu o V wierzchołkach?

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

Która struktura danych umożliwia pamięć podręczną LRU (least recently used) z operacjami get i put w O(1)?

1. AMapa mieszająca połączona z listą dwukierunkową
2. BWyłącznie binarne drzewo poszukiwań
3. CWyłącznie stos
4. DPojedyncza posortowana tablica

Musisz zachować k najmniejszych wartości ze strumienia n liczb, używając O(k) pamięci. Które podejście działa w czasie O(n log k)?

1. APosortowana tablica wszystkich n wartości
2. BKopiec minimalny przechowujący wszystkie n wartości, z którego na końcu zdejmuje się k najmniejszych
3. CKopiec maksymalny o rozmiarze k, którego korzeń zastępuje się, gdy pojawi się mniejsza wartość
4. DKolejka FIFO ostatnich k wartości