1. Algorytm przez proste wstawianie można poprawić poprzez zastosowanie:
Szybszej metody ustalenia miejsca wstawiania nowego obiektu. Najprostsze rozwiązanie to
przeszukiwanie połówkowe – próbkowanie ciągu wynikowego w środku, podział na połowę, aż do
znalezienia miejsca wstawienia nowego obiektu.

2. 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: 0

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

4. Cykl komiwojażera jest w porównaniu z cyklem Hamiltona:

5. Cyklem Eulera w spójnym grafie skierowanym nazywamy każdy cykl, który przechodzi dokładnie raz przez:

Każdą jego krawędź i powraca do początku.

6. Digraf to graf :

Digraf - Graf skierowany definiuje się jako uporządkowaną parę zbiorów. Pierwszy z nich zawiera
wierzchołki grafu, a drugi składa się z krawędzi grafu, czyli uporządkowanych par wierzchołków. Ruch po
grafie możliwy jest tylko w kierunkach wskazywanych przez krawędzie. Graf skierowany można sobie
wyobrazić jako sieć ulic, z których każda jest jednokierunkowa. Ruch pod prąd jest zakazany.

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

8. Euler w swym twierdzeniu o ścieżkach w grafach wymaga:

Według tego twierdzenia graf powinien posiadać parzystą liczbę krawędzi. Co więcej, każdy wierzchołek
grafu z wyjątkiem najwyżej dwóch, musi łączyć się z parzystą liczbą krawędzi.

9. Gdy 2 lub więcej kluczy w tablicy rozproszonej zostaje odwzorowanych w jeden i ten sam adres to mówimy o:

10. Graf planarny to graf, który nie zawiera podgrafu homeomorficznego. Jego krawędzie się nie przecinają.

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

12. Jedną z najgorszych metod sortowania jest: SORTOWANIE BĄBELKOWE

13. Jeśli graf nieskierowany jest grafem dwudzielnym to:



14. Jeśli w grafie nieskierowanym każda para wierzchołków jest połączona ścieżką, to taki graf nazywamy: SPÓJNYM

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

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

17. Kopiec definiujemy jako ciąg kluczy hl, hl+1, … , hp takich, że:
hi <= h2*i oraz hi <= h2*i+1 dla wszystkich i=l…p/2

19. Liczbę bezpośrednich potomków węzła w drzewie nazywamy jego: stopniem (tak jest na ściądze ale w necie
znalazłem taką definicje i nie wiem czy to jest to samo :

Stopień drzewa – maksymalna liczba możliwych następników dla dowolnego elementu drzewa. Najczęściej przyjmuje
się, że stopień drzewa jest potęgą liczby 2 (drzewa dwójkowe, czwórkowe, ósemkowe, szesnastkowe),

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

21. Najlepsze metody sortowania (stogowe, szybkie) mają złożoność obliczeniową rzędu:

Sortowanie stogowe : O(n * ln(n))
Sortowanie szybkie :

pesymistyczny : O(n

2

)

średni O(n*lg(n))

22. Notacja O pochodzi od słowa: (w j. ang.) – rząd – order (ang)

24. Pesymistyczny czas działania algorytmu jest górną granicą możliwego czasu działania algorytmu dla każdych
danych wejściowych; znając ten czas mamy gwarancję, że algorytm nie będzie działał dłużej.

25. Przeglądając drzewo reprezentujące wyrażenia algebraiczne uzyskano następujący rezultat: abc/+def*-*. Jest to
porządek typu: POSTORDER (POSTFIKS, wsteczny)
(według odpowiedzi z ubiegłego roku to prawda ale na necie nie udało się znaleźć potwierdzenia)

26. Sortowanie drzewiaste wykorzystuje binarne drzewo sortujące

27. Sortowanie przez wybór (selekcję) zawiera w sobie krok, polegający na wyborze klucza:

Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem
element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy
go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.

W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i
zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla
pozostałych elementów dotąd, aż wszystkie będą posortowane.

Algorytm sortowania przez wybór posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w
miejscu.


28. Sortowanie wymyślone przez C.A.R.Hoare’a to:
Sortowanie szybkie (ang.

Quicksort) (opiera się na strategii "dziel i zwyciężaj")

29. Szukanie kwadratowe to naturalna metoda uwolnienia się od grupowania kluczy w tablicy rozproszonej i wygląda
następująco:

di = (d0 + a * i + b * i2) mod p,

lub wzór uproszczony:

di = (d0 + i2)

, gdzie

d0 = h(k) - wynik początkowego haszowania klucza
di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku
wystąpił konflikt
a, b - stałe współczynniki empiryczny
i - numer kolejnego kroku szukania (0 <= i <= p)
p - liczba pozycji w tablicy

30. Ścieżka w grafie jest nazywana prostą, jeśli wszystkie jej wierzchołki są: różne

31. 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

32. W drzewie zapisanym za pomocą struktury lewolistowej:

33. W grafie prostym i skierowanym niemożliwe jest występowanie:

34. W sortowaniu stogowym wykorzystujemy drzewa: binarne

35. W tablicy rozproszonej rozwiązanie problemu kolizji polegające na przeglądaniu pamięci cyklicznie, że stałą długością
kroku: d1= (d0+a * 1) mod p nazywane jest szukaniem liniowym

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

37. Złożoność czasowa algorytmu jest to:

Czas wykonania algorytmu wyrażony funkcja rozmiaru problemu

(zależność pomiędzy liczbą operacji elementarnych wykonywanych w trakcie przebiegu algorytmu a rozmiarem danych
wejściowych (podawana jako funkcja rozmiaru tych danych)

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

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

40. Złożoność pesymistyczna wyrażona jest wzorem: T(n)=max

{T(d), d dane rozmiaru n}