1. Opisać sortowanie przez wybieranie
2. Wypisać zawartość stosu po kilku operacjach push i pop
3. Podać optymalny algorytm wyszukiwania elementu w dwukierunkowej liście wiązanej
4. Utworzyć drzewo BST i wypisać węzły w porządku inorder

1. Wyjaśnij krótko (słownie) na czym polega sortowanie przez proste wybieranie -1,5pkt
   1. Sformułuj równanie rekurencyjne i zastosuj wybraną metodę analizy algorytmów rekurencyjnych do obliczania złożoności następującego algorytmu - 3pkt

     linearSearch(int t, int index, int arr[]) //x wartosc szukana, arr - tablica z danymi o rozmiarze n
     {
     if (index == -1 || arr[index)==x) return index;
     else return (linearSearch(x, index-1);
     }
     (nie jestem pewny czy poprawnie przepisałem kod)

1. Jaki będzie stan stosu po wykonaniu następujących operacji:
   1. push(3), pop(), push(1), pop(), push(7), push(4), push(2), pop(), pop(), push(4), push(3) - 1pkt
2. podaj optymalny algorytm wyszukiwania elementu o podanej wartości w dwukierunkowej liście wiązanej - 2pkt
3. narysuj drzewo bst utworzone przez dodanie kolejno następujących liczb: 38,73,42,17,25,20,11,65,72,16 - 1,5pkt
   1. wypisz węzły drzewa w porządku inorder - 1pkt
4. wypisz węzły grafu w kolejności odwiedzania, od 1 dla algorytmu BFS - 1,5pkt, G: 1→4;; 2→1,4 ;; 3→1 ;; 4→3,5 ;; 5→3
5. wymień dwa sposoby rozwiązywania problemu kolizji w tablicy z haszowaniem - 1pkt
6. czy graf nieskierowany, który nie zawiera węzłów izolowanych jest zawsze spójny? uzasadnij odp - 2pkt
7. podaj złożoność (w notacji O ) operacji push i pop dla stosu reprezentowanego w postaci tablicy - 1pkt
8. klucze zamieszczone w węzłach bst zostaną wypisane w porządku malejącym, jeśli zostanie zastosowany algorytm przechodzenia przez drzewo w porządku:
   1. preorder
   2. inorder
   3. postorder
   4. żadna z w/w
9. kopiec jest drzewem binarnym, w którym:
   1. klucz lewego syna jest zawsze mniejszy od klucza prawego syna
   2. wszystkie poziomy są zapełnione w całości
   3. klucz prawego syna jest mniejszy od klucza ojca
   4. żadna z w/w
10. jeśli drzewo binarne jest zapisane w postaci tablicy i korzeń znajduje się w komórce o indeksie 0 to lewy potomek węzła o indeksie „i” znajduje się w komórce o indeksie… ?
11. minimalne drzewo rozpinające to graf, w którym
    1. każda para węzłów jest połączona minimalną liczbą krawędzi
    2. liczba krawędzi jest równa liczbie węzłów
    3. każdy węzeł jest co najmniej stopnia 2,
    4. żadna z w/w
12. w przeszukiwaniu w głąb grafu skierowanego nie istnieją krawędzie:
    1. w tył
    2. w przód
    3. poprzeczne
    4. żadna z w/w
13. wykonanie algorytmu Dijkstry wymaga aby graf
    1. był skierowany
    2. nie posiadał cykli
    3. nie posiadał ujemnych wag
    4. żadna z w/w
14. podaj algorytm umożliwiający wypisanie wszystkich węzłów najkrótszej ścieżki od wybranego węzła s do wybranego węzła t w grafie G, jeśli ścieżka od węzła s do t została wyznaczona przy pomocy algorytmu Dijkstry wszystkich oszacuj jego złożoność - 2pkt