algopoprawka

NAZWISKO:

IMIĘ:

DATA:

Sprawdzian nr 1 z algorytmów i struktur danych. Każde z poniższych zdań jest punktowane w sfcfij o.jq

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

2. Udowodnij, że:

(a)    0,In+101ogn = O(n)

(b)    n + togn = 0(n)

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

P

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 i j,k: integer,

3:    begln

4:    tor i :* 1 to N -1 do

S:    begln

6:

7:    for J :■ i*1 to N do

8:    IT AJJI CA(k] then

1    k s|j

10    A(k] A(i]:

11;    writeln (A)    {wypisz A[1], A[2J,........ A[NJ}

12:    end

13: end;

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

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