Pytania:
  • 2009
    1. standardowe operacje w prostych algorytmach sortowania to …. i …. elementów.
    2. algorytmem sortującym stabilnie jest: a)sortowanie bąbelkowe b)sortowanie szybkie c)sortowanie przez scalanie d)zadne z powyzszych
    3. złożoność rekurencji uniwersalnej wynika, że funkcja T(n) = a*T(n/2) + f(n) może być ograniczona asymptotycznie przez O(n^logb(a) + epsilon) jeżeli …. a przez O(f(n)) jesli…
    4. Podaj stan stosu po wykonaniu nastepujacych operacji: push(3), push(1), pop(), push(6), push(4), push(2), pop(), pop(), push(9).
    5. objaśnij skróty LIFO i FIFO.
    6. jaką złożoność w notacji O() maja operacje: push …, pop …. ,enqueue …., dequeue…, (kolejka priorytetowa)?
    7. klucze węzłach BST zostana wypisane w porzadku rosnacym jezeli zostanie zastosowany sposob przejscia przez drzewo w porządku a)preorder, b)inorder, c)postorder, d)żadna z powyższych
    8. następnikiem węzła p w BST jest węzeł…
    9. żeby usunąć z drzewa BST węzeł posiadający obydwu synów należy…
  • 2010
    1. Podać stan stosu po wykonaniu kilku różnych operacji push(x) i pop().
    2. Z rekurencji uniwersalnej wynika, że funkcja T(n) = a*T(n/2) + f(n) ma złożoność Theta(f(n)), jeśli ………. i ………….. .
    3. Przy implementacji kolejki priorytetowej na liście nieuporządkowanej złożoność dla insert to O(….), dla delete to O(….).
    4. Poprzednikiem elementu p w drzewie BST jest element ……………… .
    5. Poprzednikiem elementu p w drzewie BST, które nie ma lewego syna jest ………….. .
    6. Mamy drzewo reprezentowane na tablicy, której pierwszy indeks to 0. Lewy potomek węzła i to ………. .
    7. Zbiór to ………………………….. . Podstawowe operacje na zbiorze to ……………. i ……………. elementów.
    8. Elementy drzewa BST możemy wyświetlić w kolejności malejącej używając przeglądadania:
      • preorder
      • inorder
      • postorder
      • żadne z pow.
    9. W algorytmie Dijstry (najkrótsze drogi), graf musi:
      • cośtam
      • cośtam
      • mieć krawędzie o dodanich wagach
      • żadne z pow.
    10. W algorytmie Rabina-Karpa, wzorzec jest przesuwany względem tekstu:
      • dzięki heurystyce niezgodności
      • dzięki heurystyce najlepszego wyboru (albo jakoś tak)
      • zawsze o 1
      • żadne z pow.
    11. W kopcu:
      • lewy potomek jest mniejszy od prawego potomka
      • ma wszystkie poziomy wypełnione na maksa
      • prawy potomek jest mniejszy od ojca
      • żadne z pow.
    12. Wynikiem operacji RR na drzewie AVL o takich i takich wagach wierzchołków A i B będzie:
      • tu były 4 różne odpowiedzi
    13. Podczas przeszukiwania w głąb nie ma krawędzi:
      • poprzecznych
      • w przód
      • wstecz
      • żadne z pow.
      • (albo jakoś tak)
    14. Podstawowe operacje w algrytmach sortowania to …………. i ……………….. elementów.
    15. Opisz jakieś dziwne sortowanie grafu acyklicznego.
    16. Minimalne drzewo rozpinające to:
    17. Kopiec dwumianowy o 11 węzłach składa się z drzew dwumianowych o wagach: ………….. .
    18. Konflikty w haszowaniu rozwiązuje się przez ……………., ……………… oraz ……………… .
    19. Sortowanie przez wstawianie binarne to odmiana …………………… z użyciem ………………… w celu ………………. .
  • 2011

To samo co wyżej plus:

  1. Napisać co oznacza skrót DFS i BFS
  2. Czy graf nie posiadający węzłów izolowanym jest zawsze spójny
  3. podane był graf i należało podać kolejność wierzchołków posortowane postorder
  4. kolejka priorytetowa oparta na kopcu i należy wykonać operacje: dequeue(), dequeue(), enqueue(3) i wypisać zawartość kopca.
Materiały:
 
Zalogowany jako: test (test)
studia/przedmioty/algorytmy/egz_2009_2010_2011.txt · ostatnio zmienione: 2012/01/27 23:23 przez shimko
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki