Struktury danych: karta pracy z odpowiedziami

Czym jest graf ważony?

1. AGrafem przechowywanym na dysku
2. BGrafem, który ma więcej krawędzi niż wierzchołków
3. CGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
4. DGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość

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

1. An + 1
2. Bn
3. C2n
4. Dn − 1

Czym jest liść w drzewie?

1. AWęzłem bez dzieci
2. BWęzłem o największej wartości
3. CWęzłem z dokładnie jednym dzieckiem
4. DWęzłem bez rodzica

Węzeł binarnego drzewa poszukiwań ma prawe poddrzewo. Gdzie jest jego następnik w porządku inorder?

1. AW skrajnie lewym węźle jego prawego poddrzewa
2. BZawsze w jego rodzicu
3. CZawsze w jego prawym dziecku
4. DW skrajnie prawym węźle jego lewego poddrzewa

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

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

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(log n)
2. BO(n)
3. CO(1)
4. DO(n²)

Dlaczego serwer może losowo wybierać funkcję mieszającą z rodziny uniwersalnej?

1. ABy tablica mieszająca była posortowana
2. BBy wyeliminować potrzebę zmiany rozmiaru tablicy
3. CBy było bardzo mało prawdopodobne, że atakujący dobierze wiele kluczy, które wszystkie kolidują
4. DBy zagwarantować, że żadne dwa klucze nigdy nie będą kolidować, jakie klucze by nie wysłał atakujący

Dlaczego ze standardowego filtru Blooma nie można po prostu usuwać elementów przez zerowanie ich bitów?

1. ABitów w filtrze Blooma nie można zmieniać po jego utworzeniu
2. BUsuwanie zwiększyłoby odsetek wyników fałszywie pozytywnych do 100%
3. CTe bity mogą należeć także do innych elementów, co spowodowałoby wyniki fałszywie negatywne
4. DFiltry Blooma przechowują całe elementy, których po zahaszowaniu nie da się ponownie zlokalizować