• 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.

1. 2009_2010_2011_2_.odt