Struktury danych: karta pracy z odpowiedziami

Tablica mieszająca (hash table) przechowuje dane jako:

1. APary klucz–wartość lokalizowane przez funkcję mieszającą
2. BCiąg znaków o stałej długości
3. CWyłącznie posortowaną listę
4. DDrzewo z uporządkowanymi kluczami

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

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

1. ADostęp do elementu o indeksie i
2. BUsuwanie pierwszego elementu
3. COdczyt pierwszego elementu
4. DWstawianie na początku

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

1. AWyłącznie tablicy mieszającej
2. BKolejki
3. CKopca
4. DStosu

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

1. APrzechodzenia grafu
2. BBinarnego drzewa poszukiwań
3. CFunkcji mieszającej
4. DKolejki o stałym rozmiarze

Kolejkę zaimplementowano za pomocą dwóch stosów: push na stos „in”, a pop ze stosu „out”, który, gdy jest pusty, uzupełnia się ze stosu „in”. Jaki jest zamortyzowany koszt jednej operacji?

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

Którą własność musi spełniać drzewo czerwono-czarne?

1. AKorzeń musi być czerwony
2. BKażda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
3. CKażdy węzeł musi być czerwony
4. DKażdy czerwony węzeł musi mieć czerwone dzieci, więc czerwone węzły zawsze tworzą nieprzerwane łańcuchy aż do liści

W buforze cyklicznym front == rear może oznaczać bufor pusty albo pełny. Jaki jest popularny sposób ich rozróżnienia?

1. APrzechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
2. BUstawienie rozmiaru bufora na potęgę dwójki
3. CCzyszczenie bufora za każdym razem, gdy front równa się rear, więc stan jest pusty
4. DPrzechowywanie front i rear w tej samej zmiennej