Algorytmy i Struktury Danych

2a. Sortowanie, selekcja

1. (1p.) Podaj najmniejsz¡ i najwi¦ksz¡ mo»liw¡ liczb¦ elementów w kopcu

o wysoko±ci h.

2. (1p.) Poka», »e n-elementowy kopiec ma wysoko±¢ blg nc.
3. (1p.) Poka», »e najwi¦kszy element w poddrzewie kopca znajduje si¦ w

korzeniu poddrzewa.

4. (1p.) Gdzie w kopcu mo»na znale¹¢ element najmniejszy?
5. (1p.) Czy tablica, która jest odwrotnie posortowana, jest kopcem?
6. (1p.) Czy ci¡g < 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 > jest kopcem?
7. (1p.) Zilustruj dziaªanie Heapify(A,3) dla tablicy:

A =< 27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0 >

.

8. (2p.) Wyka», »e czas dziaªania Heapify na kopcu rozmiaru n w najgor-

szym przypadku wynosi Ω(lg n).

9. (1p.) Zilustruj dziaªanie Build-Heap dla tablicy

A =< 5, 3, 17, 10, 84, 19, 6, 22, 9 >

.

10. (1p.) Dlaczego chcemy, »eby indeks i p¦tli w wierszu 2 procedury Buid-Heap

zmniejszaª si¦ od blength[A]/2c do 1, zamiast zwi¦ksza¢ si¦ od 1 do blength[A]/2c?

11. (2p.) Poka», »e w n-elementowym kopcu istnieje co najwy»ej dn/2

h+1

e

w¦zªów o wysoko±ci h.

12. (1p.) Zilustruj dziaªanie Heapsort dla tablicy

A =< 5, 13, 2, 25, 7, 17, 20, 8, 4 >

.

13. (1p.) Jaki jest czas dziaªania Heapsort dla tablicy A o dªugo±¢i n, która

jest ju» posortowana rosn¡co (malej¡co)?

14. (2p.) Poka», »e czas Heapsort jest Ω(n lg n).
15. (1p.) Zilustruj dziaªanie Heap-Insert(A,3) dla kopca

A =< 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 >

.

16. (1p.) Opisz dziaªanie Heap-Extract-Max dla kopca

A =< 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 >

.

17. (1p.) Poka», jak za pomoc¡ kolejki priorytetowej zaimlementowa¢ zwykª¡

kolejk¦ (FIFO) i jak zaimplementowa¢ stos.

18. (2p.) Podaj dziaªaj¡c¡ w czasie O(lg n) implementacj¦ procedury Heap-Increase-Key(A,i,k),

która podstawia A[i] ← max(A[i], k) i odpowiednio zmienia struktur¦

kopca.

1

19. (2p.) Procedura Heap-Delete(A,i) usuwa element w w¦¹le i z kopca

A

. Podaj implementacj¦ Heap-Delete, która dziaªa w czasie O(lg n) dla

n

-elementowego kopca.

20. (2p.) Podaj algorytm dziaªaj¡cy w czasie O(n lg k), sªu»¡cy do scala-

nia k posortowanych list, gdzie n jest ª¡czn¡ liczb¡ elementów na listach.

(Wskazówka: U»yj kopca do k-krotnego scalania).

21. (1p.) Zilustruj dziaªanie Partition dla tablicy A =< 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21 >.

22. (1p.) Jak¡ warto±¢ q zwraca procedura Partition, gdy wszystkie ele-

menty A[p . . . r] maj¡ tak¡ sam¡ warto±¢?

23. (1p.) Podaj krótkie uzasadnienie faktu, »e czas dziaªania Partition dla

podtablicy dªugo±ci n wynosi O(n).

24. (1p.) Jak zmieni¢ procedur¦ Quicksort, »eby sortowaªa w porz¡dku nie-

rosn¡cym.

25. (1p.) Poka», »e czas Quicksort jest Θ(n lg n), gdy wszystkie elementy

tablicy A s¡ takie same.

26. (1p.) Poka», »e czas Quicksort jest Θ(n

2

)

, gdy A jest posortowana nie-

rosn¡co.

27. (1p.) Ile jest wywoªa« generatora liczb losowych Random w Randomized-Quicksort

w najgorszym przypadku? (A ile w najlepszym przypadku?)

28. (2p.) Poka», »e najlepszy czas algorytmu quicksort jest Ω(n lg n).

29. (1p.) Poka», »e q

2

+ (n − q)

2

przyjmuje maksimum w zbiorze {1, 2, . . . , n−

1}

dla q = 1 lub q = n − 1.

30. (2p.) Poka», »e oczekiwany czas Randomized-Quicksort jest Ω(n lg n)

31. (2p.) Przerabiamy algorytm quicksort nast¦puj¡co: Je±li quicksort jest

wywoªywany rekurencyjnie dla podtablicy dªugo±ci mniejszej ni» k, to nic

nie robi. Po zako«czeniu quicksort dla caªej tablicy, uruchamiamy na niej

insertion-sort. Poka», »e tak przerobiony algorytm ma oczekiwany czas

dziaªania O(nk + n lg(n/k)). Jakie s¡ najkorzystniejsze warto±ci k?

2