Zadania z egzaminu, 1 termin 2011/2012

Treść:

  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


Komplet pytań:

  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