ZESTAW B
1. Gdy 2 lub więcej kluczy w tablicy rozproszonej zostaje odwzorowanych w ten sam adres to mówimy o:
a. wypełnieniu podwójnym
b. dublowaniu
c. kolizjach ( konfliktach )
d. zapełnieniu całkowitym
2. Liczbę bezpośrednich potomków węzła w drzewie nazywamy jego:
a. głębokością
b. stopniem
c. wysokością
d. dziećmi ( potomkami )
3. Jeżeli obiekt składa się z siebie samego lub jego definicja odwołuje się do niego samego, to taki obiekt nazywamy:
a. indukcyjnym
b. rekurencyjnym
c. sekwencyjnym
d. strukturalnym
4. Przeglądając podane drzewo metoda „preorder”, kolejność odwiedzania wierzchołków jest następująca:
a. 4,2,7,8,5,6,3,1
b. 2,4,1,7,5,8,3,6
c. 1,2,3,4,5,6,7,8
d. 1,2,4,3,5,7,8,6 | nie pamiętam jakie drzewo było na egzaminie |
5. Funkcja T(n) = 2n^3 + 3n^2 + 4n +5 jest:
a. O(n^3)
b. O(n^2)
c. O(n)
d. O(1)
6. Załóżmy, że elementami tablicy są liczby: 5,11, 15, 25, 18, 26, 17, 27, 23, 20. Czy tablica ta reprezentuje stóg?
a. stogu nie można zapisać w tablicy
b. Tak
c. Nie
d. Może, ale nie musi
7. Algorytm Kruskala w podanym grafie znajdzie:
a. Jedno minimalne drzewo rozpinające o koszcie 24
b. Nie znajdzie minimalnego drzewa rozpinającego
c. Jedno minimalne drzewo rozpinające o koszcie 25
d. Dwa minimalne drzewa rozpinające o koszcie 24 | nie pamiętam grafu z egzaminu |
8. Czy podany graf jest grafem eulerowskim?
a. Tak
b. Jest grafem półeulerowskim
c. Nie
d. Nie da się powiedzieć | nie pamiętam jaki tam był graf |
9. Podany ciąg wierzchołków (E-G-D-E-C-F-B) dla podanego grafu reprezentuje:
a. łuk
b. cykl
c. pętlę
d. ścieżkę
10. Czy podane kody znaków mogą tworzyć kod Huffmana? (`A'-0,'C'-101,'E'-100,'G'-111,'X'-1101,'Q'-0100)
a. Tak
b. Nie w żadnym przypadku
c. Tak, ale po usunięciu kodu dla litery `G'
d. Nie można tak kodować znaków
11. Złożoność czasowa algorytmu jest to:
a. Czas wykonania algorytmu wyrażony funkcja rozmiaru problemu
b. Szybkość wzrostu zajętości pamięci i czasu
c. Czas wykonania algorytmu jako funkcja dyskretna zależna od jakości sprzętu komputerowego
d. Czas wykonania algorytmu mierzony w sekundach
12. Sortowanie przez wybór ( selekcje ) zawiera w sobie krok, polegający na wyborze klucza:
a. minimalnego
b. mediany
c. średniego
d. zerowego
13. Jeśli graf nieskierowany jest grafem dwudzielnym to:
a. liczba wierzchołków została podzielona przez dwa
b. liczba krawędzi została podwojona
c. zbiór wierzchołków podzielony został na dwa rozdzielne podzbiory
d. zbiór krawędzi został rozdzielony na dwa rozdzielne podzbiory
14. Złożoność obliczeniowa wyszukiwania w tablicy rozproszonej jest rzędu:
a. O(n)
b. O(k)
c. O(n^2)
d. O(log2n)
15. Sortowanie drzewiaste wykorzystuje:
a. Drzewo BST
b. Medianę
c. Binarne drzewo sortujące
d. Stóg
16. Który spośród niżej podanych ciągów kluczy, może opisywać kolejność odwiedzania wierzchołków w procesie wyszukiwania w drzewie BST.
a. 4,2,7,8,5,6,3,1
b. 2,4,1,7,5,8,3,6
c. 1,2,4,3,5,7,8,6
d. 8,7,6,5,4,3,2,1
17. Graf kubiczny jest to:
a. Graf, którego nie można narysować na płaszczyźnie
b. Graf regularny rzędu 3
c. Graf planarny stopnia 2
d. Nie ma takiego grafu
18. Cykl Hamiltona w grafie to:
a. Zamknięta ścieżka przechodząca dokładnie jeden raz przez każdą krawędź grafu
b. Cykl związany z mostami w Królewcu
c. Zamknięta ścieżka przechodząca dokładnie jeden raz przez każdy wierzchołek grafu
d. Dowolna zamknięta trasa w grafie
19. Stos jest to struktura danych z algorytmem dostępu:
a. LIFO
b. FIFO
c. ASCII
d. LILO
20. Algorytmy Prima i Kruskala dotyczą:
a. Cyklu Hamiltona
b. Cyklu Eulera
c. Problemu komiwojażera
d. Minimalnego drzewa rozpinającego