studia:przedmioty:algorytmy:egz_2009_2010_2011 [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.

== Pytania: ==
  * **2009**
    - standardowe operacje w prostych algorytmach sortowania to .... i .... elementów. 
    - algorytmem sortującym stabilnie jest: a)sortowanie bąbelkowe b)sortowanie szybkie c)sortowanie przez scalanie d)zadne z powyzszych 
    -  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... 
    - Podaj stan stosu po wykonaniu nastepujacych operacji: push(3), push(1), pop(), push(6), push(4), push(2), pop(), pop(), push(9). 
    - objaśnij skróty LIFO i FIFO. 
    - jaką złożoność w notacji O() maja operacje: push ..., pop .... ,enqueue ...., dequeue..., (kolejka priorytetowa)? 
    - 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 
    - następnikiem węzła p w BST jest węzeł... 
    - żeby usunąć z drzewa BST węzeł posiadający obydwu synów należy... 
  * **2010**
    - Podać stan stosu po wykonaniu kilku różnych operacji push(x) i pop().
    - Z rekurencji uniwersalnej wynika, że funkcja T(n) = a*T(n/2) + f(n) ma złożoność Theta(f(n)), jeśli .......... i .............. . 
    - Przy implementacji kolejki priorytetowej na liście nieuporządkowanej złożoność dla insert to O(....), dla delete to O(....). 
    - Poprzednikiem elementu p w drzewie BST jest element .................. . 
    - Poprzednikiem elementu p w drzewie BST, które nie ma lewego syna jest .............. . 
    - Mamy drzewo reprezentowane na tablicy, której pierwszy indeks to 0. Lewy potomek węzła i to .......... . 
    - Zbiór to ................................ . Podstawowe operacje na zbiorze to ................ i ................ elementów. 
    - Elementy drzewa BST możemy wyświetlić w kolejności malejącej używając przeglądadania:
      * preorder 
      * inorder 
      * postorder 
      * żadne z pow. 
    - W algorytmie Dijstry (najkrótsze drogi), graf musi: 
      * cośtam 
      * cośtam 
      * mieć krawędzie o dodanich wagach 
      * żadne z pow. 
    - 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. 
    - 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. 
    - 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 
    - Podczas przeszukiwania w głąb nie ma krawędzi: 
      * poprzecznych 
      * w przód 
      * wstecz 
      * żadne z pow. 
      * (albo jakoś tak) 
    - Podstawowe operacje w algrytmach sortowania to ............. i .................... elementów. 
    - Opisz jakieś dziwne sortowanie grafu acyklicznego. 
    - Minimalne drzewo rozpinające to: 
    - Kopiec dwumianowy o 11 węzłach składa się z drzew dwumianowych o wagach: .............. . 
    - Konflikty w haszowaniu rozwiązuje się przez ................, .................. oraz .................. . 
    - Sortowanie przez wstawianie binarne to odmiana ........................ z użyciem ..................... w celu ................... .

* **2011**
      To samo co wyżej plus:
    - Napisać co oznacza skrót DFS i BFS
    - Czy graf nie posiadający węzłów izolowanym jest zawsze spójny 
    - podane był graf i należało podać kolejność wierzchołków posortowane postorder
    - kolejka priorytetowa oparta na kopcu i należy wykonać operacje: dequeue(), dequeue(), enqueue(3) i wypisać zawartość kopca.

== Materiały: ==
  - {{:studia:przedmioty:algorytmy:egzamin:2009_2010_2011_2_.odt|}}

Opis zmian Mniejsze zmiany