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(n2)
ś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}