Struktury danych: karta pracy z odpowiedziami

Która operacja ma złożoność O(1) dla tablicy, ale O(n) dla listy jednokierunkowej?

1. AWstawianie na początku
2. BOdczyt pierwszego elementu
3. CUsuwanie pierwszego elementu
4. DDostęp do elementu o indeksie i

Czym jest cykl w grafie?

1. AWierzchołkiem bez krawędzi
2. BŚcieżką, która zaczyna się i kończy w tym samym wierzchołku
3. CŚcieżką, która odwiedza każdy wierzchołek
4. DKrawędzią o wadze zero

Na czym polega własność kopca maksymalnego (max-heap)?

1. AKlucze są posortowane od lewej do prawej
2. BWszystkie liście zawierają klucz maksymalny
3. CKlucz każdego lewego dziecka jest większy lub równy kluczowi jego prawego rodzeństwa
4. DKlucz każdego rodzica jest większy lub równy kluczom jego dzieci

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

1. AO(n²), bo każdy element przesuwa się n razy
2. BO(1), bo indeks jest znany
3. CO(log n), z powodu wyszukiwania binarnego
4. DO(n), bo dalsze elementy trzeba przesunąć

Przejście in-order (poprzeczne) binarnego drzewa poszukiwań odwiedza klucze w kolejności:

1. ARosnącej (posortowanej)
2. BZawsze malejącej
3. CPoziomami
4. DWstawiania

Bufor cykliczny (ring buffer) jest powszechnie używany do implementacji:

1. AKolejki o stałym rozmiarze
2. BPrzechodzenia grafu
3. CFunkcji mieszającej
4. DBinarnego drzewa poszukiwań

Filtr Blooma potrafi odpowiedzieć na pytanie „czy ten element należy do zbioru?”:

1. AZawsze dokładnie
2. BTylko dla liczb
3. CZ możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych
4. DZ możliwymi fałszywie ujemnymi wynikami, ale bez fałszywie dodatnich

Klucze 5, 3, 8, 1 wstawia się w tej kolejności do pustego binarnego kopca minimalnego opartego na tablicy. Jak wygląda końcowa tablica?

1. A[1, 3, 5, 8]
2. B[3, 1, 8, 5]
3. C[1, 3, 8, 5]
4. D[1, 5, 8, 3]