ASD ep 08 2003 D 3

Zadanie 6

Niech będzie dany dowolny n-elemcntowy ciąg.

(a)    Szukamy elementu drugiego co do wielkości następującą metodą:

a.    Wszystkie elementy ciągu umieszczamy w drzewie AVL.

b.    Znajdujemy i usuwamy element minimalny.

c.    Znajdujemy ponownie element minimalny.

Oszacuj koszt tego algorytmu? Odpowiedź uzasadnij

Koszt........................

Uzasadnienie...........................................................

(b)    Ile co najwyżej porównań trzeba wykonać, jeżeli do wyszukania elementu drugiego co do wielkości używamy metody:

c.    sekwencyjnego przeglądania ciągu.........................................

d.    turniej...................................

Zadanie 7

Rozważmy kopiec zawierający 150 elementów, zaimplementowany w tablicy T, w której na pozycji T[ I ] znajduje się element minimalny.

(a)    Podaj indeksy, pod którymi znajdują się ojciec i prawy syn elementu T[7].

ojciec................................. prawy syn.......................................

(b)    Ile elementów można dołożyć do tego kopca, tak by nie zwiększyć jego wysokości? (odpowiedź uzasadnij)

Liczba elementów:....................................Uzasadnienie....................................

(c) Jak znaleźć dowolny element w kopcu (dozwolone są jedynie operacje insert, dclmin, empty)? Zaproponuj metodę postępowania i oszacuj jej koszt w przypadku, gdy kopiec ma n elementów.

Koszt zaproponowanego algorytmu...................

Algorytm :

Zadanie 8

(a) Wyjaśnij, jakie problemy należą do klasy P.

(b) Podaj przykład problemu z tej klasy.