𝑓

1

𝑛 =

3𝑛

2

+ 10𝑛 + 2000

2 𝑛

, 𝑓

2

𝑛 = 𝑙𝑜𝑔

100

𝑛

𝑛

2

,

𝑓

3

𝑛 =

8 𝑛 + 2𝑛

𝑛 + 20

, 𝑓

4

𝑛 = 𝑙𝑜𝑔

2

2

𝑛

3

+ 6𝑛

2

void sort(int a[], int n)
{ int v, i, j;
for (i=1; i<n; ++i){
v=a[i];
for (j=i-1; j>=0 && a[j]>v; --j)
a[j+1]=a[j];
a[j+1]=v;}
}

2, 2, 2, …, 2, 1
n, 1, 2, 3, …, n–1

3.2. Z drzewa usuwamy węzeł
o wartości 2 i przywracamy
(jeśli to konieczne) drzewu
własności AVL równoważąc
drzewo jak najmniejszą liczbą
rotacji węzłów. Narysuj tak
powstałe nowe drzewo (rys.
1.) i podaj pary węzłów i
kierunki ich

3.3. Następnie dodajemy
węzeł 9. Narysuj

6, 2, 8, 1, 3, 4, 9, 7, 5

A i

4.2. Czy graf posiada drogę Eulera? ………………..

4.3. Czy w graf ma cykl Eulera? ……………………

4.4. Zastosuj algorytm Dijkstry w celu wyznaczenia odległości
wierzchołka A od pozostałych.

T

D[A] D[B] D[C] D[D] D[E] D[F] D[G]

{B,C,D,E,F,G}

0

12

Inf.

Inf.

Inf.

Inf.

1

{B, C, D, E, F}

0

12

Inf.

7

Inf.

Inf.

1

{B, C, E, F}

0

11

Inf.

7

14,5

9

1

{B, C ,E}

0

11

12

7

10,5

9

1

{B, C}

0

11

12

7

10,5

9

1

{C}

0

11

12

7

10,5

9

1

{ }

0

11

12

7

10,5

9

1

4.5. Stosując algorytm Kruskala wyznaczyć (w odpowiedniej
kolejności) krawędzie

minimalnego drzewa rozpinającego.

………………………………………………………………….

Sumaryczna waga drzewa wynosi ……………………………..

4.6. Wyznaczyć:
a) maksymalny przepływ ……………………………..
b) czy bez zmiany przepływu można usunąć jakieś krawędzie?
……………………………………………………………..
Jeśli tak, to które? …………………………………………

f

3

,

f

1

, f

2

, f

4

n

3

n

3

n

n

3, 2, 1, 6, 4, 8, 7, 10

1, 2, 3, 4, 6, 7, 8, 10

1, 2, 4, 7, 10, 8, 6, 3

(3, 6) – w lewo

3

---

A,B,C,E,F,D,G,D,F,E,C,B,A

A,B,G,C,D,F,E

TAK

NIE

|AG| |BC| |EF| |CE| |DF| |DG|

13,5