Zadania z egzaminu

1 termin 2012/2013

Treść:

  1. Wyjaśnij krótko (słownie) na czym polega wyszukiwanie binarne -1pkt
  2. podaj optymalny algorytm (w języku C) usuwania dwukierunkowej listy wiązanej - 2pkt
  3. 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)
  4. wymień dwa sposoby rozwiązywania problemu kolizji w tablicy z haszowaniem - 1pkt
  5. wymień po jednym algorytmie sortowania o podanych złożonościach obliczeniowych: O(n), O(nlogn), O(n^2)
  6. jak wyznaczyć spójne składowe w grafie nieskierowanym za pomocą algorytmu BFS
  7. 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ć:
  8. 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
  9. w przeszukiwaniu w głąb grafu skierowanego nie istnieją krawędzie:
    1. w tył
    2. w przód
    3. poprzeczne
    4. wszystkie powyższe istnieją
  10. 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
  11. 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
  12. Drzewo dwumianowe 4rtego stopnia będzie miało … węzłów.
  13. Kopiec dwumianowy o 11 węzłach składa się z drzew dwumianowych o wagach: ………….. .
  14. Do wyważenia następującego drzewa należy zastosować rotacje: a)LL b)RR c) LR d)RL

lub:

  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);
     }
     

2 termin 2012/2013

To co powyżej +

  1. Omówić krótko sortowanie przez wstawianie.
  2. Co i jak wpływa na złożoność obliczeniową algorytmu Dijkstry.
  3. W jaki sposób za pomocą algorytmu DFS można wyznaczyć silnie spójne składowe w grafie
  4. Wypisać kolejność odwiedzania wierzchołków z algorytmu BFS podanego grafu
  5. Napisać algorytm w C odwracania listy jednokierunkowej wiązanej , określić złożoność i objaśnić
  6. Napisać algorytm w C rozmieszczenia elementów względem elementu osiowego + złożoność obliczeniowa + wyjaśnienie
 
Zalogowany jako: test (test)
studia/przedmioty/algorytmy/egz_2013.txt · ostatnio zmienione: 2013/02/07 12:23 przez monika
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki