===== Zadania z egzaminu, 1 termin 2011/2012 =====

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

\\
{{:studia:przedmioty:algorytmy:img_20120202_112215.jpg?400|}}


=== Komplet pytań: ===
  - Wyjaśnij krótko (słownie) na czym polega sortowanie przez proste wybieranie -1,5pkt
    -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)

  - Jaki będzie stan stosu po wykonaniu następujących operacji:
    -push(3), pop(), push(1), pop(), push(7), push(4), push(2), pop(), pop(), push(4), push(3)   - 1pkt
  - podaj optymalny algorytm wyszukiwania elementu o podanej wartości w dwukierunkowej liście wiązanej - 2pkt
  - narysuj drzewo bst utworzone przez dodanie kolejno następujących liczb: 38,73,42,17,25,20,11,65,72,16 - 1,5pkt
    -wypisz węzły drzewa w porządku inorder - 1pkt
  - 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
  - wymień dwa sposoby rozwiązywania problemu kolizji w tablicy z haszowaniem - 1pkt
  - czy graf nieskierowany, który nie zawiera węzłów izolowanych jest zawsze spójny? uzasadnij odp - 2pkt
  - podaj złożoność (w notacji O ) operacji push i pop dla stosu reprezentowanego w postaci tablicy - 1pkt
  - 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:
    -preorder 
    -inorder 
    -postorder 
    -żadna z w/w
  - kopiec jest drzewem binarnym, w którym:
    -klucz lewego syna jest zawsze mniejszy od klucza prawego syna 
    -wszystkie poziomy są zapełnione w całości 
    -klucz prawego syna jest mniejszy od klucza ojca 
    -żadna z w/w
  - 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... ?
  -minimalne drzewo rozpinające to graf, w którym 
    -każda para węzłów jest połączona minimalną liczbą krawędzi 
    -liczba krawędzi jest równa liczbie węzłów 
    -każdy węzeł jest co najmniej stopnia 2, 
    -żadna z w/w
  -w przeszukiwaniu w głąb grafu skierowanego nie istnieją krawędzie:
    -w tył
    -w przód
    -poprzeczne
    -żadna z w/w
  -wykonanie algorytmu Dijkstry wymaga aby graf
    -był skierowany
    -nie posiadał cykli
    -nie posiadał ujemnych wag
    -żadna z w/w
  -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