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}