EGZAMIN 2005

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 węzł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. Najlepsze 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)