2asdegzam6wrzesien2004

c. jeśli X zapisano jako drzewo BST

5.    Dany jest pewien zbiór Q punktów na płaszczyźnie.

a) Podaj warunek, który gwarantuje, że koszt algorytmu Jarvisa konstrukcji otoczki wypukłej dla zbioru Q

będzie liniowy? Warunek:    .....................................................................................

h) Jaki jest koszt algorytmu Grahama? ..............................

c) Jakiej struktury pomocniczej używa algorytm Grahama? ........................................

6.    (a) Uporządkuj następujące algorytmy sortowania ze względu na ich średni koszt czasowy zaczynając od algorytmu o najmniejszym koszcie: InsertionSort, MergeSort. HeapSort.

(b) Czy można podać przykład takiego ciągu o 8 elementach, dla którego algorytm InsertionSort będzie miał koszt liniowy?

(c) Jaki jest koszt pesymistyczny każdego z wymienionych wyżej algorytmów zastosowanych do ciągu o n elementach?

InsertionSort.........................................MergeSort...........................................HeapSort.....................................

7. (a) Znajdź najkrótsze ścieżki od wierzchołka E do pozostałych wierzchołków algorytmem Dijkstry. Zaznacz na grafie drzewo najkrótszych ścieżek.

(b) Wypisz kolejność w jakiej były akceptowane krawędzie............................................................

(g)    Wypisz wierzchołki uzyskanego drzewa najkrótszych ścieżek w porządku BFS i DFS

BFS:................................................... DFS:..........................................................................

(h)    Niech X i Y będą dwoma wyróżnionymi wierzchołkami pewnego grafu. Czy drzewa najkrótszych

ścieżek o korzeniach w X i w Y muszą być identyczne ? TAK/NIE.................................

(i)    Czy droga z pewnego wierzchołka C do D w drzewie najkrótszych ścieżek o korzeniu w X jest

najkrótszą drogą łączącą te wierzchołki w oryginalnym grafie? TAK/NIE...............................

(j)    Czy droga z C do D musi mieć w obu drzewach najkrótszych ścieżek o korzeniu w X i o korzeniu w Y

odpowiednio, taką samą długość? TAK/NIE..............