ASD ep 06 2003 1

EGZAMIN ASD POPRAWKOWY//KURS 2003

16 czerwiec 2003

Imię i nazwisko studenta........................................................ nr indeksu....................

GRUPA B

21.    Algorytm QuickSort.

a.    Wypisz zawartość tablicy T={4,8,l,5,0,7,6,2_r3} po jednokrotnym zastosowaniu do niej procedury split

(mediana - pierwszy element).............................

b.    Jaki jest średni koszt tego algorytmu jeśli zastosujemy go do k-elementowego ciągu losowo wybranych

elementów? .................................

22.    Rozważmy algorytm CountSort (przez zliczanie)

a.    Wypisz zawartość pomocniczej tablicy zliczeń po posortowaniu za pomocą

tego algorytmu tablicy T={ 6,4,2,1,2,1,9,1}    ......................................................

b.    Podaj pesymistyczną złożoność pamięciową tego algorytmu, wyjaśniając

co oznaczają użyte parametry:............................................................................

23.    Ile porównań wykona algorytm InsertionSort sortując tablicę T={2,5,8,1,7,6,9,3} ?................

24.    Dla każdego z wymienionych algorytmów sortowania 2000-elementowego ciągu liczb naturalnych mniejszych od 1000 oszacuj liczbę wykonanych porównań elementów:

a.    SelectionSort ............................................................

b.    RadixSort ............................................................

c.    HeapSort .............................................................

25.    Do początkowo pustego drzewa BST włożono po kolei następujące klucze:

4,2,1,3,7,10,9,6,8.

a.    Narysuj po prawej stronie powstałe drzewo.

b.    Narysuj drzewo jakie powstanie po usunięciu klucza 4

c.    Jaka jest przeciętna złożoność czasowa operacji delete na słowniku

zaimplementowanym jako BST?.....................................

26. Do drzewa na rysunku a) poprzedniego zadania

a.    dorysuj współczynniki zrównoważenia i

b.    jeśli nie jest to drzewo AVL, narysuj drzewo po dokonaniu stosownej rotacji.

27.    Rozważmy kopiec zawierający 500 elementów, zaimplementowany za pomocą tablicy T[l:500] (w korzeniu jest element minimalny)

a.    Jaki jest indeks ojca elementu znajdującego się pod indeksem 113?......

b.    Jaka jest wysokość tego kopca?.......................................

28.    Uporządkuj podany ciąg funkcji, ze względu na rosnący rząd wielkości: n=2^l‘^<l!"^,+lg(n^J), f2=20n + n , f3=3n + n!, fW + 3\ fW + n²lg(n)

29. Zaznacz formuły, które są prawdziwe:

a.    (2n)! = 0(4")

b.    4^3d = 0(4")

c.    2lg(n!)= 0(2'*^n!>)