4000865427

Egzamin z ASD

Część testowa 04.03.2009

1.    (1 pkt.) Podkreśl algorytmy sortowania, które dla niektórych danych wejściowych złożonych z n różnych wartości działają w czasie U(n^{1 2}):

'InsertionSort, MergeSort, QuickSort. 'StdectionSoft,

2.    (2 pkt.) Podaj liczbę permutacji zbioru {1} (gdzie n > 2), dla

których algorytm InsertionSort bez strażnika wykonuje dokładnie n — 1 porównań elementów tablicy.    tr Ł

3.    (1 pkt.) Początkowa zawartość tablicy to [1.10,2,8.3^7,4.6,5]. Podaj jej zawartość po fazie konstrukcji kopca w standardowej implementacji algorytmu Heapsort (sortującego rosnąco).

(

O,*,

/

c, r, n

)

\ <,2.

4.    (1 pkt.) Jaki jest koszt algorytmu Dijkstry dla grafu o n wierzchołkach i m krawędziach z zastosowaniem kopca Fibonacciego jako kolejki priorytetowej?

/w ^ -h    ^

5.    (1 pkt.) Podaj równanie rekurencyjne na oczekiwany koszt algorytmu

Quicksort.    Tfr) =    T-^-1

6.    (2 pkt.) Podaj liczbę permutacji zbioru {1,2,..., 15} takich, że elemen

tem, względem którego zostanie dokonany podział ciągu w algorytmie selekcji metodą ,,magicznych piątek”, jest 8.    ^

i ■    (ii)' - (* &M3

7.    (1 pkt.) Jaki jest oczekiwany koszt znajdowania mediany w ciągu n-

elementowym algorytmem Hoare’a?    Oć-3

8.    (2 pkt.) Podaj przykład najmniejszej uniwersalnej rodziny funkcji buszujących {1,2,3,4, 5} —> {1,2} (w postaci tabelki wartości każdej z funkcji).

1

   2 3 4 .T

hi

2

h'2