1. Co rozumiemy pod pojęciem algorytmu poprawnego wg Floyda?
To taki algorytm, który dla każdego egzemplarza problemu zatrzymuje się i daje dobry wynik

2. Pesymistyczny czas działania algorytmu jest jego:
górną

3. Złożoność czasowa algorytmu jest to:
Czas wykonania algorytmu wyrażony funkcją rozmiaru problemu

4. Złożoność pamięciowa algorytmu wyrażona jest funkcją:
S(n)

5. Algorytm przez proste wstawianie można poprawić poprzez zastosowanie:
wstawianie klucza z wartością 0

6. Sortowanie wymyślone przez CA.R.Hoare'a to:
sortowanie przez podział (quick-sort)

7. Obiekt nie większy (mniejszy lub równy) połowie n obiektów oraz nie mniejszy (większy lub równy) od drugiej połowy n obiektów to obiekt:
mediana

8. Kopiec definiujemy jako ciąg kluczy hi, hi+1... ,hp takich, że:
hi<=h2i i hi<=h2i+1

9. W tablicy rozproszonej rozwiązanie problemu kolizji polegające na przeglądaniu pamięci cyklicznie, że stałą długością kroku: d|" (do+a-i) mod p nazywane jest szukaniem
liniowym

10. Ścieżka w grafie jest nazywana prostą, jeśli wszystkie jej wierzchołki są:
a) położone na linii prostej b) równe
c) różne d) współliniowe

11. Digraf to graf:
skierowany

12. Minimalne drzewo rozpinające w grafie nieskierowanym łączy wszystkie wierzchołki grafu tak, aby łączna waga drzewa była:
minimalna

13. Binarne drzewo zrównoważone to drzewo, w którym dla każdego węzła liczby węzłów w jego lewym i prawym poddrzewie różnią się co najwyżej o:
1

14. Jeżeli obiekt składa się z siebie samego lub jego definicja odwołuje się do niego samego, to taki obiekt nazywamy:
rekurencyjnym

15. Złożoność obliczeniowa wyszukiwania w tablicy rozproszonej jest rzędu:
O(n)

16. Sortowanie drzewiaste wykorzystuje:
binarne drzewo sortujące

17. Graf, w którym każdy wierzchołek ma ten sam stopień nazywamy:
regularnym

18. Długość ścieżki hierarchicznej do wezła na poziomie k w drzewie jest równa:
k-1

19. W drzewie zapisanym za pomocą struktury lewolistowej:
A(B(D(I),E(J,K,L))',C(F(O),G(M,N),H(P)))
liczba węzłów na poziomie 2 wynosi:
2

20. W binarnym drzewie poszukiwań, dla każdego węzła wszystkie klucze z lewego poddrzewa są w stosunku do klucza w tym węźle:
mniejsze

21. W binarnym drzewie poszukiwań, dla każdego węzła wszystkie klucze z prawego poddrzewa są w stosunku do klucza w tym węźle:
większe

22. Klasa problemów P (polonomial) zawiera wszystkie problemy rozwiązywalne w czasie wielomianowym, a więc takie, które rozwiązuje w co najwyżej czasie wielomianowym:
deterministyczna maszyna Turinga

23. Złożoność pesymistyczna wyrażona jest wzorem:
Tpes(n)=max{T(d), d-dane rozmiaru n}

24. Notacja O pochodzi od słowa (z jęz. ang):
rząd

25. Jedną z najgorszych metod sortowania jest:
sortowanie bąbelkowe

26. Nąjlepsze metody sortowania (stogowe, szybkie) mają złożoność obliczeniową rzędu:
nlog2n

27. Szukanie kwadratowe to naturalna metoda uwolnienia się od grupowania kluczy w tablicy rozproszonej i wygląda następująco:
hi=(ho+a*i+b*i2) mod p

28. Jeśli w grafie nieskierowanym każda para wierzchołków jest połączona ścieżką, to taki graf nazywamy:
spójnym

29. Euler w swym twierdzeniu o ścieżkach w grafach wymaga:
Parzystej liczby krawędzi wychodzących z każdego wierzchołka

30. Który z podanych algorytmów nie jest algorytmem tworzenia minimalnego drzewa rozpinającego:
Dijkstry

31. W teorii grafów nie istnieje następujące pojęcie:
graf Euklidesa

32. Liczbę bezpośrednich potomków węzła w drzewie nazywamy jego:
Stopniem

33. Przeglądając drzewo reprezentujące wyrażenia algebraiczne uzyskano następujący rezultat: abc/+def*-* jest to porządek typu:
postorder (postfiks, wsteczny)

---