alg1

NAZWISKO:

IMIĘ:

DATA:

Sprawdzian nr l z algorytmów i struktur danych. Każde z poniższych zdań jest punktowane w skali 0-10.

1.    Podaj klasyfikację typowych funkcji pod względem tempa wzrostu.

2.    Udowodnij, żc:

(a)    0,ln * lOlogn - O(n)

(b)    n + log n = 0(n)

(c)    n² + 2sin(n) = Q(n²)

(d)

3. Przedstaw wydruk wykonany przez procedurę PW, wywołaj ją od tablicy A = {01,05,60,50,30}

1: proceduro PW (var A: Tab);

2:    var ij.k : integer;

3:    begin

4:    for i:» 1 to N -1 do

5:    begin

6:    k :■!;

7:    for j :■ i+1 to    N do

8

9:

10

11

12

ifAfll <A[k] then

k :=]; m:-: A[i];

wnteln(A)    {wypisz A{1J. A[2}......... AIN]>

end

13: end;

4. Oblicz złożoność obliczeniową powyższego algorytmu.

5. Przedstaw metody rozwiązywania kolizji metodami łańcuchowania.