Struktury danych: karta pracy z odpowiedziami

Graf składa się z:

1. AWyłącznie kluczy i skrótów
2. BWierzchołków (węzłów) połączonych krawędziami
3. CWierszy i kolumn
4. DTylko korzenia i liści

Czym są węzły rodzeństwa (siblings) w drzewie?

1. AWęzłem i jego rodzicem
2. BWęzłami, które mają tego samego rodzica
3. CWęzłami, które nie mają dzieci
4. DWęzłami na tej samej głębokości w różnych poddrzewach

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

1. ANa ostatniej pozycji tablicy
2. BW którymś liściu, którego trzeba szukać
3. CW korzeniu
4. DW skrajnie lewym liściu

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

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

Ile pamięci zajmują listy sąsiedztwa dla grafu o V wierzchołkach i E krawędziach?

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

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²)

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

1. AZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
2. BZamianę go z korzeniem
3. CUsunięcie całego poddrzewa
4. DZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy

Jaki jest pesymistyczny koszt pojedynczej operacji find w strukturze union-find z n elementami bez łączenia według rangi (union by rank) i bez kompresji ścieżek?

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