ASD II rok informatyki
G.Mirkowska

                        Testy   Pytania  Zadania

SPIS TRESCI

Wszystkie niezbędne definicje, oznaczenia i twierdzenia można znaleźć w dokumentach:
WYKŁADY
CWICZENIA
 
Ewentualne zmiany, uwagi, poprawki i pytania  proszę kierować na adres::
 
Grażyna Mirkowska
pokój 301, 3-cie piętro , PJWSTK
Warszawa, ul. Koszykowa 82
E-mail mirkowska
Konsultacje: poniedziałki godz. 15-17

 
     
                                                                                                               SPIS TRESCI

    STRUKTURY  DANYCH

    Pytania, zadania i testy dotyczą tylko struktur omawianych na wykładzie  ASD - dotyczyć więc będą tablic, list,algebry Boolea, struktury stosów, kolejek, słownikow, kolejek priorytetowych, drzew BST, drzew AVL, struktury kopca, 2-3 drzewa, B-drzewam struktura FIND-UNION.
     

     

  1. Dane są zbiory A i B reprezentowane jako drzewa AVL, card(A) =n1 i card(B)= n2. Napisać program wypisujący przecięcie zbiorów A i B. Przeanalizować koszt czasowy i pamięciowy algorytmu.
  2. Idealnie wyważonym drzewem BST nazywamy takie drzewo BST, w którym dla każdego wierzchołka v prawdziwa jest następująca własnosć: liczby elementów w lewym i prawym poddrzewie wierzchołka  różnią się co najwyżej o 1.
    1. Napisać program tworzący idealnie wyważone drzewo BST z danego drzewa BST o n wierzchołkach. (złożonosć O(n))
    2. Udowodnić lub obalić następujące twierdzenie: w idealnie wyważonym drzewie BST wszystkie liscie znajdują się na 2 ostatnich poziomach.
  3. Niech D będzie klasą drzew binarnych lokalnie pełnych (tzn. rząd każdego wierzchołka wynosi 0 lub 2). Niech pp(d) oznacza słowo otrzymane w wyniku odczytania  etykiet drzewa w porządku wzdłużnym (preorder).
    1. Odczytać słowo pp(d) dla danego drzewa d.
    2. Napisać program rekurencyjny, który kopiuje dane drzewo d i nadaje ;u etykiety zgodne z pewnym danym odwzorowaniem  f: A -> N.
    3. Napisać program iteracyjny, który dla danego drzewa BST wypisuje słowo pp(d). Jaki jest koszt tego algorytmu?
    4. Niech u będzie słowem nad alfabetem A oraw Nf(u) liczbą etykiet lisci w tym słowie a Ni(u) liczbą etykiet wierzchołków wewnętrznych w tym słowie. Udowodnić, że Ni(u) +1= Nf(u).
    5. Napisać program, który odpowiada na pytanie czy dane słowo pp(d)  jest palindromem. Zbadać koszt tego algorytmu.
    6. Dane są dwa drzewa d1 i d2 należące do D. Zbadać czy słowo pp(d1) jest podsłowem  pp(d2).
    7. Napisać algorytm znajdowania częsci wspólnej słów pp(d1) i pp(d2).
     
  4. Dla każdej z wymienionych własnosci wskaż struktury drzewiaste(BST, AVL, KOPIEC, 2-3Drzewo, B-Drzewo), w których jest ona prawdziwa:
      1. wszystkie liscie znajdują się na co najwyżej dwóch ostatnich poziomach
      2. etykiety wszystkich dróg od korzenia do liscia tworzą ciągi uporządkowane
      3. wszystkie drogi od korzenia doliscia mają tę samą długosć
      4. etykiety na każdym poziomie drzewa tworzą ciągi uporządkowane.
  5. Udowodnić, że w pełnym drzewie binarnym, kopcu, 2-3 drzewie, B-drzewie liczba lisci jest zawsze wieksza niż liczba wierzchołków wewnętrznych (Zbadać  tę zależnosć w drzewie BST i AVL).
  6. Udowodnić, że w każdym kopcu liczba lisci jest co najwyżej o 1 większa niż liczba wierzchołków wewnętrznych.
  7. Uzasadnić, że koszt usunięcia dowolnego elementu z kopca o n elementach jest w najgorszym razie rzędu (n+lg n). Uproscić to oszacowanie.
  8. Dany jest ciąg liczb : 5,1,0,4,7,3,9. Utworzyć drzewa BST i AVL wstawiając kolejno elementy ciagu do początkowo pustego drzewa. Jaka jest maksymalna i minimalna wysokosć drzewa (odpowiednio BSt i AVL) zawierającego elementy danego ciągu?
  9. Ile maksymalnie rotacji trzeba wykonać, aby wstawić dany element do drzewa AVL o wysokoci h i 2 h+1 -1 wierzchołkach?
  10. Czy jest prawda, że sredni koszt włożenia m elementów do drzewa BST zawierającego już n elementów wynosi Teta(lg(nm))? Odpowiedź uzasadnij.
  11. Jaka jest minimalna ilosć lisci w  drzewie d o wysokosci h, jesli d jest odpowiednio drzewem BST, AVL, 2-3 drzewem, kopcem?

    12.  

     
     c.d.                                                                                                  SPIS TRESCI

    WERYFIKACJA

     Pytania zawarte w tej częsci dotyczą pojęć poprawnosci całkowitej, poprawnosci częsciowej i stopu  programów oraz sposobów ich dowodzenia. Podstawowymi metodami (stosowananymi i zalecanymi) są metoda opisów Floyda-Hoare i metoda niezmienników.
     
  12. Niech A będzie następującym algorytmem

    13. begin
        p:=2; bool := true;
        while (p*p <n+1 and bool) do
               if n mod p = 0 then bool := false fi;
               p := p+1
        od
    end
    1. Podać niezmiennik pętli while wystepującej w tym algorytmie wiedząc, że n jest liczbą naturalną. Uzasadnić wybór.
    2. Podać warunek końcowy WK, by algorytm A byłpoprawny względem specyfikacji  <WP, WK>, gdzie WP ={n>1, n jest liczbą naturalną}
    3. Uzasadnić poprawnosć algorytmu A względem wybranej w punkcie poprzednim specyfikacji.
    4. Oszacować koszt czasowy  algorytmu.
       c.d.                                                                                               SPIS TRESCI  

    SPECYFIKACJA

    Zadania przedstawione w tej częsci dotyczą specyfikowania struktur danych, sprawdzania poprawnosci specyfikacji, np. jej niesprzecznosci i/lub pełnosci, weryfikowania implementacji względem podanej specyfikacji struktury.
     
     
  13. Kolejka dwustronna to taka, w której operacje wkładania elementu (Linsert, Rinsert) i usuwania elementu (Ldelete, Rdelete) mogą się odbywać z obu końców. Niech będzie sygnatura struktury kolejek dwustronnych
                    <E+ D, Linsert, Rinsert, Ldelete, Rdelete, Lfin, Rfin, empty, = >
    gdzie E jest zbiorem elementów a D zbiorem kolejek a operacje mają następujące typy
        Linsert, Rinsert : E x D -> D
        Ldelete, Rdelete : D -> D
        Lfin, Rfin : D-> E
        empty : D -> {0,1}
    Uzupełnić specyfikację tej struktury.
 
     c.d.                                                                                                         SPIS TRESCI

    ZŁOŻONOSĆ

    Ta grupa zadań dotyczy głównie obliczania złożonosci czasowej i pamięciowej konkretnych algorytmów, porównywania złożonosci różnych rozwiązań tego samego problemu, porównywanie i szacowanie rzędów funkcji, własnosci notacji asymptotycznej. Kilka pytań dytyczy problemów trudnych i zupełnych.
     
  1.  Które z następujących własnosci są prawdziwe i dlaczego?
      1. n3 + log nn = Omega(n3)
      2. 2 log n = Teta(n)
      3. Suma{0< i <n : log i} = O(n)
      4. n2 + n3 = Teta(n3)
      5. log(n n) = O(n)
      6. log Suma{0< i <n : i} = Omega(n)
      7. O(nlog(n)) = (n+log(n))2
      8. Teta(n3) = log(n!)
      9. Omega(xn) = Suma(xi : 0<i<n)   gdzie  x >1
  2. Niech będzie dany graf spójny G = <V, E>, gdzie card(V)= n card(E)= m. Koszt algorytmu Kruskala znajdowania minimalnego drzewa rozpinającego ma rzad taki sam jak funkcja:
      1.     n3
      2.     m2* log n
      3.     n * log m
      4.     m * log m
      5.     inna odpowiedź (jaka?)
  3. Elementy zbioru X={xn, xn-1 , ...x1 } zostały włożone do stosu S w kolejnosci xn, xn-1 , ...x1. Zaznaczyć własciwą liczbę operacji push i pop w procesie usuwania elementu xi z S.
      1. 2*(i-1) push   +    i   pop
      2. 2*(n-i) push   +    1  pop
      3. (i-1)     push   +    i  pop
      4. inna odpowiedz (jaka?)
       
  4. Która z wymienionych równoci jest zawsze prawdziwa, jeżeli wiadomo, że g(n)=O(f) i h(n)=O(f)
    1. g(n) + h(n) = O(f)
    2. g(n) * h(n) = O(f)
    3. f(n) + g(n) = O(f)
  5. Uporządkować następujące funkcje ze względu na ich rosnący rząd wielkosci:

    6. f1(n) = abs(sin2(n)), f2(n) = lg(n2), f3(n) = lg(n!) , f4(n) = 0.001 n2.
    Odpowiedź uzasadnić.
  6. Ciąg Fibonacci'ego definiuje się rekurencyjnie następująco:
      7. f(1)=f(0)=1, f(n+1) = f(n) + f(n-1) pour n>0
     

     

     

     c.d.                                                                                                 SPIS TRESCI

    ALGORYTMY

    Zadania zgromadzone w tej częsci służa przypomnieniu algorytmów poznanych w trakcie wykładu (Algorytmy realizujące operacje wkładania, szukania, usuwania elementu ze zbioru reprezentowanego przy pomocy różnych struktur danych. Algorytmy wyszukiwania minimum i maksimum, elememtu 2giego co do wielkosci, elementu k-tego co do wielkosci. Algorytmy sortowania przez porównywanie elementów: inserion-sort, selection-sort, Shell-sort, quick-sort
    Sortowanie z użyciem kolejki priorytetowej. Sortowanie przez rozrzucanie.
    Sortowanie zewnętrzne. Algorytmy geometryczne: otoczka wypukła, przecinanie odcinków, najbliżej położone punkty.Algorytmy wyszukiwania wzorca : sekwencyjny, Rabina-Karpa, Boyer-Moor.)
    lub konstruowania i implementacji  nowych algorytmów, szacowania ich kosztów oraz ich analizy.
     
  7. Zaproponuj algorytm wyszukiwania wszystkich elementów z  danego drzewa BST, które należą do pewnego danego przedziału (a,b). Oszacuj koszt czasowy tego algorytmu.
  8. Napisać algorytm wyliczania częsci całkowitej logarytmu przy podstawie 3 z dowolnej liczby naturalnej.
    1. Podać specyfikację tego algorytmu.
    2. Zapisać algorytm używając czterech podstawowych instrukcji. przypisania, składaniam instrukcji warunkowej, instrukcji iteracji.
    3. Uzasadnić całkowitą poprawnosć algorytmu względem podanej specyfikacji.
    4. Okreslić rząd funkcji kosztu zaproponowanego algorytmu.
  9. Stosując zasadę "dziel i zwyciężaj" zaproponuj algorytm wyznaczania miejsca zerowego funkcji ciągłej f(x) w przedziale (a,b) z zadaną dokładnoscią eps.

    10.                                                                                                                      SPIS TRESCI

    INNE

    Zadania zebrane w tej częsci dotyczą pojęć o charakterze podstawowym, które nie mieszczą się w poprzednich działach lub mają charakter teoretyczny. Dotyczą podstawowych pojęć takich jak:
    Operacja,  bijekcja, homomorfizm, izomorfizmstruktur danych.
    Relacja, porządek, równoważnosć, kongruencja.
    Sumy postępu arytmetycznego i geometrycznego.
    Rozwiązywanie równań rekurencyjnych.
    Spełnianie i prawdziwosć formuł.
    Obliczalnosć. Teza Churcha.
    Rozstrzygalnosć, Nierozstrzygalnosć .
     
     
  10. Podać przykład formuły spełnionej w strukturze liczb naturalnych, która nie jest z tej strukturze prawdziwa.
  11. Podać przykład formuły, która jest prawdziwa w strukturze stosów i która jest falsyfikowalna w strukturze kolejek.
  12. Czy prawdziwe jest zdanie: ponieważ każdy kopiec jest drzewem binarnym, to każda własnosć przysługująca kopcowi jest prawdziwa w strukturze drzew binarnych.
  13. Ułóż równanie rekurencyjne opisujące funkcję kosztu czasowego algorytmu MergeSort.
  14. Czy relacja r zdefiniowana następująco w zbiorze programów jest czy nie jest relacją równoważnosci?(P1, P2 - dwa dowolne programy)

    15. "P1 r  P2  wtedy i tylko wtedy gdy wyniki programów są takie same dla tych samych danych początkowych".
     
     

                                                                                                                     SPIS TRESCI

    Przykladowe pytania na egzamin ustny.

    1      2      3      4      5      6
     

    1.
    (a) Czy następująca formula jest zawsze prawdziwa?
    ((- empty(delete(p)) & p=insert(e,p)) =>  mb(e,p)) =>   (-empty(delete(p)) =>  (p=insert(e,p) => mb(e,p))

    (b) Omówić algorytmy wyszukiwania i wkładania elementu do B-drzewa. Oszacować złożonosć tych algorytmów.
     

    2.
    (a) Podać pełną specyjfikacją abstrakcyjnej struktury stosów. Czy następująca struktura danych jest stosem?
    (b) Opisać ogólną postać algorytmu sortowania z użyciem kolejki priorytetowej. Jakie są koszty tego algorytmu jesli kolejka jest zaimplementowana jako 2-3 drzewo.
     
     

    3.
    (a) Podać pełną specyfikację abstrakcyjnej struktury kolejek.Czy następująca struktura danych jest kolejką.
    (b) Narysować drzewa BST, AVL i kopiec,  wiedząc, że powstały one przez włożenie kolejno elementów e1, e2,e3,...,e5 do drzewa początkowo pustego, oraz, że e1,...e5 tworzą ciąg rosnący.
     

    4.
    (a) Sformułować pojecie częsciowej poprawnosci algorytmu.Uzasadnić, że następujący algorytm jest poprawny ze względu na  nastepujacą specyfikację.
    (b) Podać przykład algorytmu działającego w oparciu o zasadę "dziel i zwyciężaj".
     

    5.
    (a) Sformułować twierdzenie o reprezentacji dla stosów.
    (b) Podać dwa różne algorytmy wyszukiwania elementu w ciągu uporządkowanym.Porównać koszty.

    6.
    (a) Zaprezentować idee metody Floyda-Hoare badania poprawnosci algorytmu. Zastosować tę metodę do dowodu czesciowej poprawnosci następującego algorytmu ze względu na  specyfikację WP= x<y ,WK=? :
    ( x := x+1;  y := y*z).
    (b) Podać co najmniej dwa różne algorytmy równoszesnego wyszukiwania  min i max. Jakie jest ograniczenie dolne złożonosci tego problemu?.