studia:przedmioty:algorytmy:egz_2013 [Informatyka WIEIK PK

Zredaguj tę stronę i naciśnij zapisz.

Na stronie ze składnią znajdziesz opis znaczników wiki. Jeśli chcesz poćwiczyć zajrzyj do piaskownicy.

===== Zadania z egzaminu =====

===== 1 termin 2012/2013 =====

=== Treść: ===
  - Wyjaśnij krótko (słownie) na czym polega wyszukiwanie binarne -1pkt
  - podaj optymalny algorytm (w języku C) usuwania dwukierunkowej listy wiązanej - 2pkt
  - Węzły drzewa BST utworzonego kolejno z liczb: 48, 73, 42, 17, 25, 20, 11, 65, 72 wypisane w porządku postorder (lub inorder)
  - wymień dwa sposoby rozwiązywania problemu kolizji w tablicy z haszowaniem - 1pkt
  - wymień po jednym algorytmie sortowania o podanych złożonościach obliczeniowych: O(n), O(nlogn), O(n^2)
  - jak wyznaczyć spójne składowe w grafie nieskierowanym za pomocą algorytmu BFS
  - kolejka priorytetowa reprezentowana za pomocą kopca binarnego min po następujących operacjach : insert (7), insert (4) insert (2), insert (8), insert(1), erase () będzie miała postać:
  - 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
  -w przeszukiwaniu w głąb grafu skierowanego nie istnieją krawędzie:
    -w tył
    -w przód
    -poprzeczne
    -wszystkie powyższe istnieją
   - podaj algorytm (kod w C)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
   - algorytm Boyera-Moore'a:jeśli //symbol nie występuje we wzorcu// to //s=j//, jeśli //symbol występuje na prawo od j// to //s=1//, jeśli //symbol występuje na lewo od j// to //s=j//
   - Drzewo dwumianowe 4rtego stopnia będzie miało ... węzłów.
   - Kopiec dwumianowy o 11 węzłach składa się z drzew dwumianowych o wagach: ………….. .
   - Do wyważenia następującego drzewa należy zastosować rotacje: a)LL b)RR c) LR d)RL  
{{:studia:przedmioty:algorytmy:rt1.jpg|}}lub:{{:studia:przedmioty:algorytmy:rt2.jpg|}}
   - 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);
       }

===== 2 termin 2012/2013 ===== 
To co powyżej +
  - Omówić krótko sortowanie przez wstawianie. 
  - Co i jak wpływa na złożoność obliczeniową algorytmu Dijkstry.
  - W jaki sposób za pomocą algorytmu DFS można wyznaczyć silnie spójne składowe w grafie  
  - Wypisać kolejność odwiedzania wierzchołków z algorytmu BFS podanego grafu
  - Napisać algorytm w C odwracania listy jednokierunkowej wiązanej , określić złożoność i objaśnić
  - Napisać algorytm w C rozmieszczenia elementów względem elementu osiowego + złożoność obliczeniowa + wyjaśnienie

Opis zmian Mniejsze zmiany