1. Metoda "meet in the middle":
a )polega na rozwiązaniu mniejszych podproblemów i scaleniu wyniku
b )jest tak na prawdę zastosowaniem programowania dynamicznego
c )musi wykorzystywać maski bitowe
d )może być szybsza niż sprawdzanie wszystkich możliwości
2. Dany jest zbiór płaskich talerzy. Po umyciu czyste talerze dokładane są na górę.
Jeśli potrzeba talerzy do posiłku, to pobiera się je z góry.
Za pomocą której z poniższych struktur danych najlepiej reprezentować zbiór talerzy?
a )lista jednokierunkowa
b )lista dwukierunkowa
c )stos
d )kolejka
3. Które z poniższych struktur danych nadają się do efektywnej implementacji przeszukiwania metodą BFS?
a )kolejka
b )lista dwukierunkowa
c )stos
d )lista jednokierunkowa
4. Które z sytuacji mogą mieć miejsce w drzewie BST?
a )klucze wszystkich potomków pewnego wierzchołka są mniejsze od jego klucza
b )klucz lewego syna pewnego wierzchołka jest większy niż klucz jego prawego syna
c )klucze wszystkich potomków pewnego wierzchołka są większe od jego klucza
d )wszystkie wierzchołki w lewym poddrzewie mają klucze nie większe niż klucz korzenia
5. Dany jest graf o 5-ciu wierzchołkach i krawędziach między nimi (początek, koniec, długość):
(1,2,2), (2,3,3), (3,4,4), (5,4,1), (5,1,3), (2,5,3), (5,3,1).
Jaka jest waga minimalnego drzewa rozpinającego?
a )6
b )5
c )7
d )9
e )8
6. Ile wspólnych węzłów mają ścieżki od liści reprezentujących końce przedziału [1,3] do korzenia w drzewie reprezentującym przedział [0,7]?
a )2
b )3
c )4
d )5
7. Jaką wartość zwraca atan2(1, 0) ?
a )-pi
b )pi/2
c )90
d )0
8. Dany jest tekst T o długości n oraz k wzorców długości co najmniej 1, których łączna długość to m.
Wzorce są parami różne. Zakładamy, że rozmiar alfabetu jest stały.
Wskaż poprawne górne ograniczenia na czas działania algorytmu Aho-Corasicka.
a ) O(nk + m)
b ) O(n + m + k)
c ) O(n + m log m + k)
d ) O(nm)
9. Do pustego drzewa BST wrzucamy kolejno wartości: 2, 4, 3, 1, 5, 6.
a )wierzchołek o kluczu 4 jest korzeniem
b )wierzchołek o kluczu 3 jest synem tego o kluczu 4
c )wierzchołek o kluczu 4 ma dwóch synów
d )najdłuższa możliwa ścieżka przy szukaniu jakiejś wartości składa się z 3 wierzchołków
e )drzewo to spełnia warunek zrównoważania drzewa AVL
10. Przypomnijmy rozwiązanie problemu zliczania przecięc odcinków poziomych z pionowymi. Miotła przesuwa się z lewej w prawą i używa drzewa potęgowego. Dla każdej współrzędnej pamięta ile odcinków poziomych się pod nią znajduje. Gdy napotykamy poziomy odcinek, dodajemy go do miotły, gdy odcinek poziomy się kończy, jest on usuwany, w przypadku gdy pod miotłą znajdzie się odcinek pionowy, zliczamy przecięcia z odcinkami w miotle. W przypadku, gdy na danej współrzędnej x znajduje się wiele zdarzeń, najpierw dodajemy nowe odcinki, następnie zliczamy przecięcia, po czym usuwamy kończące się odcinki poziome. Gdybyśmy najpierw rozpatrzyli zdarzenia rozpoczynania i kończenia się odcinków poziomych, a następnie zliczali przecięcia z odcinkami pionowymi, to wynik:
a )może być mniejszy niż przed zmianą
b )jeśli współrzędne x wszystkich zdarzeń są od siebie różne, to nie zmieni się
c )może być większy niż przed zmianą
d )nie zmieni się, ta zamiana jest nieistotna
11. Które stwierdzenia są prawdziwe dla drzewa przedziałowego typu (+,max) ?
a )operacja query(a,b ) zwraca sumę dotychczasowych wstawień do punktów z przedziału domkniętego [a,b]
b )jeśli na pustym drzewie wykonamy insert(5,5,1) a następnie insert(6,6,-1) to operacja query(4,6) zwróci liczbę 1
c )operacja insert(a,b,v) doda obciążenie v do punktu b
d )jeśli query(1,2) = 4 i query(3,4) = 5 to na pewno query(1,4) = 9
12. Ile węzłów (włącznie z korzeniem) ma drzewo TRIE reprezentujące zbiór słów {"abc", "abcd", "bcd", "bac"} ?
a )10
b )9
c )5
d )4
13. W przestrzeni znajduje się n punktów. Wybieramy płaszczyznę, która dzieli zbiór punktów na dwie części. Ile różnych podziałów możemy co najwyżej uzyskać? Podaj wynik z dokładnością do rzędu wielkości.
a )n^2
B) więcej niż wielomianowo wiele
c )n
d )n^3
14. W kopcu, który służy do znajdowania minimum, przy kopcowaniu elementu w dół, aktualnie przetwarzany element zamienia się ewentualnie z:
a )jego synem o mniejszej wartości
b )jego synem o większej wartości
c )jego ojcem
d )jego dowolnym synem
15. Dany jest tekst T o długości n oraz k wzorców długości co najmniej 1, których łączna długość to m.
Wzorce są parami różne. Zakładamy, że rozmiar alfabetu jest stały.
Wskaż poprawne górne ograniczenia na czas działania algorytmu Aho-Corasicka.
a ) O(nk + m)
b ) O(nm)
c ) O(n + m + k)
d ) O(n + m log m + k)
16. Na ile minimalnie przedziałów bazowych można rozłożyć przedział [1,7] ?
a ) 1
b )3
c )4
d )2
17. Jaka jest złożoność algorytmu Kruskala, przy sortowaniu krawędzi w czasie O(E log E) i sprawdzaniu, czy dwa wierzchołki należą do tej samej spójnej za pomocą metody przeszukiwania DFS, wywoływanej dla każdej krawędzi (wskaż najlepsze oszacowanie)?
a ) O(V * V)
b ) O(V * V * log E)
c ) O(V log V)
d ) O(V * E)
e ) O(E log E)
18. Ile wspólnych węzłów mają ścieżki od liści reprezentujących końce przedziału [1,3] do korzenia w drzewie reprezentującym przedział [0,7]?
a ) 2
b ) 4
c ) 5
d ) 3
19. Podzbiory zbioru {a, b, c, d} zapisujemy jako maski bitowe, przy czym kolejne bity odpowiadają kolejnym literkom (najniższy bit odpowiada literce a, a najwyższy - d). Jaka maska odpowiada podzbiorowi {a, c, d}?
a )13
b )5
c )7
d )9
e )11
20. Do pustego drzewa BST wrzucamy kolejno wartości: 2, 4, 3, 1, 5, 6.
a )najdłuższa możliwa ścieżka przy szukaniu jakiejś wartości składa się z 3 wierzchołków
b )wierzchołek o kluczu 4 jest korzeniem
c )drzewo to spełnia warunek zrównoważania drzewa AVL
d )wierzchołek o kluczu 4 ma dwóch synów
e )wierzchołek o kluczu 3 jest synem tego o kluczu 4
21. Mamy dane zmienne a i b będące maskami pewnych zbiorów. Zaznacz zdania prawdziwe:
a ) a & b to suma zbiorów a i b
b ) (a | b ) ^ b to różnica zbiorów a i b
c ) a ^ b to część wspólna zbiorów a i b
d ) a & (~b ) to różnica zbiorów a i b
22. Dany jest graf o 5-ciu wierzchołkach i krawędziach między nimi (początek, koniec, długość):
(1,2,2), (2,3,3), (3,4,4), (5,4,1), (5,1,3), (2,5,3), (5,3,1).
Jaka jest waga minimalnego drzewa rozpinającego?
a ) 8
b ) 7
c ) 5
d ) 9
e ) 6
23. Mamy dane zmienne a i b będące maskami pewnych zbiorów. Zaznacz zdania prawdziwe:
a ) a ^ b to część wspólna zbiorów a i b
b ) (a | b ) ^ b to różnica zbiorów a i b
c ) a & (~b ) to różnica zbiorów a i b
d )a & b to suma zbiorów a i b
24. Rozważmy popularne rozwiązanie problemu FIND-UNION (reprezentacji zbiorów rozłącznych) przez pamiętanie drzewa dla każdego zbioru. Stosujemy kompresję ścieżek oraz korzystamy z głębokości drzewa pamiętanej w każdym korzeniu. Jaka jest maksymalna wysokość drzewa?
a ) logarytmiczna ze względu na liczbę krawędzi
b ) logarytmiczna ze względu na liczbę wierzchołków
c )liniowa ze względu na liczbę wierzchołków
d )liniowa ze względu na liczbę krawędzi
25. Które zdania są prawdziwe?
a )spośród elementów stosu jako pierwszy opuści go ten, który przyszedł najpóźniej
b )element, który jako pierwszy przyjdzie do kolejki, opuści ją jako pierwszy
c )element, który jako ostatni przyjdzie do kolejki, opuści ją jako pierwszy
d )spośród elementów stosu jako pierwszy opuści go ten, który przyszedł najwcześniej
26. Rozważmy drzewo TRIE reprezentujące zbiór słów {"acd", "bac"} wraz z obliczonymi polami suf_link i dict_link. Które zdania są prawdziwe ?
a ) dict_link węzła "bac" to węzeł "ac"
b )dict_link węzła "acd" to korzeń
c )suf_link węzła "bac" to węzeł "ac"
d )suf_link węzła "acd" to korzeń
a )polega na rozwiązaniu mniejszych podproblemów i scaleniu wyniku
b )jest tak na prawdę zastosowaniem programowania dynamicznego
c )musi wykorzystywać maski bitowe
d )może być szybsza niż sprawdzanie wszystkich możliwości
2. Dany jest zbiór płaskich talerzy. Po umyciu czyste talerze dokładane są na górę.
Jeśli potrzeba talerzy do posiłku, to pobiera się je z góry.
Za pomocą której z poniższych struktur danych najlepiej reprezentować zbiór talerzy?
a )lista jednokierunkowa
b )lista dwukierunkowa
c )stos
d )kolejka
3. Które z poniższych struktur danych nadają się do efektywnej implementacji przeszukiwania metodą BFS?
a )kolejka
b )lista dwukierunkowa
c )stos
d )lista jednokierunkowa
4. Które z sytuacji mogą mieć miejsce w drzewie BST?
a )klucze wszystkich potomków pewnego wierzchołka są mniejsze od jego klucza
b )klucz lewego syna pewnego wierzchołka jest większy niż klucz jego prawego syna
c )klucze wszystkich potomków pewnego wierzchołka są większe od jego klucza
d )wszystkie wierzchołki w lewym poddrzewie mają klucze nie większe niż klucz korzenia
5. Dany jest graf o 5-ciu wierzchołkach i krawędziach między nimi (początek, koniec, długość):
(1,2,2), (2,3,3), (3,4,4), (5,4,1), (5,1,3), (2,5,3), (5,3,1).
Jaka jest waga minimalnego drzewa rozpinającego?
a )6
b )5
c )7
d )9
e )8
6. Ile wspólnych węzłów mają ścieżki od liści reprezentujących końce przedziału [1,3] do korzenia w drzewie reprezentującym przedział [0,7]?
a )2
b )3
c )4
d )5
7. Jaką wartość zwraca atan2(1, 0) ?
a )-pi
b )pi/2
c )90
d )0
8. Dany jest tekst T o długości n oraz k wzorców długości co najmniej 1, których łączna długość to m.
Wzorce są parami różne. Zakładamy, że rozmiar alfabetu jest stały.
Wskaż poprawne górne ograniczenia na czas działania algorytmu Aho-Corasicka.
a ) O(nk + m)
b ) O(n + m + k)
c ) O(n + m log m + k)
d ) O(nm)
9. Do pustego drzewa BST wrzucamy kolejno wartości: 2, 4, 3, 1, 5, 6.
a )wierzchołek o kluczu 4 jest korzeniem
b )wierzchołek o kluczu 3 jest synem tego o kluczu 4
c )wierzchołek o kluczu 4 ma dwóch synów
d )najdłuższa możliwa ścieżka przy szukaniu jakiejś wartości składa się z 3 wierzchołków
e )drzewo to spełnia warunek zrównoważania drzewa AVL
10. Przypomnijmy rozwiązanie problemu zliczania przecięc odcinków poziomych z pionowymi. Miotła przesuwa się z lewej w prawą i używa drzewa potęgowego. Dla każdej współrzędnej pamięta ile odcinków poziomych się pod nią znajduje. Gdy napotykamy poziomy odcinek, dodajemy go do miotły, gdy odcinek poziomy się kończy, jest on usuwany, w przypadku gdy pod miotłą znajdzie się odcinek pionowy, zliczamy przecięcia z odcinkami w miotle. W przypadku, gdy na danej współrzędnej x znajduje się wiele zdarzeń, najpierw dodajemy nowe odcinki, następnie zliczamy przecięcia, po czym usuwamy kończące się odcinki poziome. Gdybyśmy najpierw rozpatrzyli zdarzenia rozpoczynania i kończenia się odcinków poziomych, a następnie zliczali przecięcia z odcinkami pionowymi, to wynik:
a )może być mniejszy niż przed zmianą
b )jeśli współrzędne x wszystkich zdarzeń są od siebie różne, to nie zmieni się
c )może być większy niż przed zmianą
d )nie zmieni się, ta zamiana jest nieistotna
11. Które stwierdzenia są prawdziwe dla drzewa przedziałowego typu (+,max) ?
a )operacja query(a,b ) zwraca sumę dotychczasowych wstawień do punktów z przedziału domkniętego [a,b]
b )jeśli na pustym drzewie wykonamy insert(5,5,1) a następnie insert(6,6,-1) to operacja query(4,6) zwróci liczbę 1
c )operacja insert(a,b,v) doda obciążenie v do punktu b
d )jeśli query(1,2) = 4 i query(3,4) = 5 to na pewno query(1,4) = 9
12. Ile węzłów (włącznie z korzeniem) ma drzewo TRIE reprezentujące zbiór słów {"abc", "abcd", "bcd", "bac"} ?
a )10
b )9
c )5
d )4
13. W przestrzeni znajduje się n punktów. Wybieramy płaszczyznę, która dzieli zbiór punktów na dwie części. Ile różnych podziałów możemy co najwyżej uzyskać? Podaj wynik z dokładnością do rzędu wielkości.
a )n^2
B) więcej niż wielomianowo wiele
c )n
d )n^3
14. W kopcu, który służy do znajdowania minimum, przy kopcowaniu elementu w dół, aktualnie przetwarzany element zamienia się ewentualnie z:
a )jego synem o mniejszej wartości
b )jego synem o większej wartości
c )jego ojcem
d )jego dowolnym synem
15. Dany jest tekst T o długości n oraz k wzorców długości co najmniej 1, których łączna długość to m.
Wzorce są parami różne. Zakładamy, że rozmiar alfabetu jest stały.
Wskaż poprawne górne ograniczenia na czas działania algorytmu Aho-Corasicka.
a ) O(nk + m)
b ) O(nm)
c ) O(n + m + k)
d ) O(n + m log m + k)
16. Na ile minimalnie przedziałów bazowych można rozłożyć przedział [1,7] ?
a ) 1
b )3
c )4
d )2
17. Jaka jest złożoność algorytmu Kruskala, przy sortowaniu krawędzi w czasie O(E log E) i sprawdzaniu, czy dwa wierzchołki należą do tej samej spójnej za pomocą metody przeszukiwania DFS, wywoływanej dla każdej krawędzi (wskaż najlepsze oszacowanie)?
a ) O(V * V)
b ) O(V * V * log E)
c ) O(V log V)
d ) O(V * E)
e ) O(E log E)
18. Ile wspólnych węzłów mają ścieżki od liści reprezentujących końce przedziału [1,3] do korzenia w drzewie reprezentującym przedział [0,7]?
a ) 2
b ) 4
c ) 5
d ) 3
19. Podzbiory zbioru {a, b, c, d} zapisujemy jako maski bitowe, przy czym kolejne bity odpowiadają kolejnym literkom (najniższy bit odpowiada literce a, a najwyższy - d). Jaka maska odpowiada podzbiorowi {a, c, d}?
a )13
b )5
c )7
d )9
e )11
20. Do pustego drzewa BST wrzucamy kolejno wartości: 2, 4, 3, 1, 5, 6.
a )najdłuższa możliwa ścieżka przy szukaniu jakiejś wartości składa się z 3 wierzchołków
b )wierzchołek o kluczu 4 jest korzeniem
c )drzewo to spełnia warunek zrównoważania drzewa AVL
d )wierzchołek o kluczu 4 ma dwóch synów
e )wierzchołek o kluczu 3 jest synem tego o kluczu 4
21. Mamy dane zmienne a i b będące maskami pewnych zbiorów. Zaznacz zdania prawdziwe:
a ) a & b to suma zbiorów a i b
b ) (a | b ) ^ b to różnica zbiorów a i b
c ) a ^ b to część wspólna zbiorów a i b
d ) a & (~b ) to różnica zbiorów a i b
22. Dany jest graf o 5-ciu wierzchołkach i krawędziach między nimi (początek, koniec, długość):
(1,2,2), (2,3,3), (3,4,4), (5,4,1), (5,1,3), (2,5,3), (5,3,1).
Jaka jest waga minimalnego drzewa rozpinającego?
a ) 8
b ) 7
c ) 5
d ) 9
e ) 6
23. Mamy dane zmienne a i b będące maskami pewnych zbiorów. Zaznacz zdania prawdziwe:
a ) a ^ b to część wspólna zbiorów a i b
b ) (a | b ) ^ b to różnica zbiorów a i b
c ) a & (~b ) to różnica zbiorów a i b
d )a & b to suma zbiorów a i b
24. Rozważmy popularne rozwiązanie problemu FIND-UNION (reprezentacji zbiorów rozłącznych) przez pamiętanie drzewa dla każdego zbioru. Stosujemy kompresję ścieżek oraz korzystamy z głębokości drzewa pamiętanej w każdym korzeniu. Jaka jest maksymalna wysokość drzewa?
a ) logarytmiczna ze względu na liczbę krawędzi
b ) logarytmiczna ze względu na liczbę wierzchołków
c )liniowa ze względu na liczbę wierzchołków
d )liniowa ze względu na liczbę krawędzi
25. Które zdania są prawdziwe?
a )spośród elementów stosu jako pierwszy opuści go ten, który przyszedł najpóźniej
b )element, który jako pierwszy przyjdzie do kolejki, opuści ją jako pierwszy
c )element, który jako ostatni przyjdzie do kolejki, opuści ją jako pierwszy
d )spośród elementów stosu jako pierwszy opuści go ten, który przyszedł najwcześniej
26. Rozważmy drzewo TRIE reprezentujące zbiór słów {"acd", "bac"} wraz z obliczonymi polami suf_link i dict_link. Które zdania są prawdziwe ?
a ) dict_link węzła "bac" to węzeł "ac"
b )dict_link węzła "acd" to korzeń
c )suf_link węzła "bac" to węzeł "ac"
d )suf_link węzła "acd" to korzeń