aisd d

Zestaw D Imię Nazwisko

Indeks

1	2	3	4	5	6	SUMA	OCENA

1.    Po uruchomieniu funkcji drukującej B-drzewo rzędu 2 warstwami (najpierw korzeń, potem bezpośredni potomkowie itd.) uzyskano następujący wydruk : 10, 3, 5, 7, 15, 1,4,6, 9, 14, 17.

a)    narysuj to drzewo ( 2 pkt.)

b)    usuń z niego klucz 14 (pokaż jak to się robi) (3 pkt.)

2.    Poniżej podano własności dwóch algorytmów sortowania (a i b). Jakie to algorytmy. (5 pkt.)

algorytm	sortowana struktura	opt.	porównania przepisania (zamiany) śr. pesym. opt. śr. pesym.	stabilność	najlepszy najgorszy ciąg ciąg
a	tablica	n	n^2/4 n^2/2 0 n^2/4 n^2/2	tak	uporz.	odwr. uporz.
b	lista	n log	n n log n n^2/2 n log n n log n n log n	nie	nie ma	uporz. i odwr. uporz.

3.    Do drzewa BST wstawiono kolejno klucze : 6, 4, 10,1, 12, 2, 8 , a następnie uruchomiono funkcję licz. struct wezel{int klucz; int liczba; wezel* lewy; wezel* prawy ;};

typedef wezel* Wsk; int licz(Wsk w)

{ if (!w) return 0;

return (w->liczba=licz(w->lewy)+licz(w->prawy)+

((w->lewy && !w->prawy |) w->prawy && !w->lewy) ? 1 : 0));} Wyświetl w kolejności przeglądania drzewa postorder (LPW) wartości pól: klucz i liczba ( 5 pkt.).

4.    Dana jest prosta jednokierunkowa lista o początku q zawierająca elementy: {10,20,30,40,50,60,70} Napisz co robi funkcja Fun oraz wyświetl zawartość list p i q po wywołaniu : p=Fun(q);

struct element {TDane dane;element* nast;}; typedef element* Wsk;

Wsk Fun(Wsk &a)

{Wsk pom=NULL;

if(a && a->nast){pom=a->nast;a->nast=pom->nast;pom->nast=Fun(a->nast);} return pom;}

5.    W tablicy heap zapisano elementy n elementowej kolejki zrealizowanej za pomocą stogu zupełnego ( element na wierzchołku stogu ma najmniejszy klucz). Napisz funkcję void zwiększ (tab heap, int n, int poz, unsigned int zmiana) zwiększającą wartość klucza elementu wskazanego przez indeks poz o wartość zmiana ( wiąże się to z koniecznością przywrócenia własności stogu) (5 pkt.).

6.    Algorytm PRIMA znajdowania minimalnego drzewa rozpinającego ( MST). Dana jest macierz sąsiedztwa grafu

	A	B	C	D	E	F
A		1	8
B	1		5	2	7
C	8	5			1
D		2			3	5
E		7	1	3		1
F				5	1

narysuj ten graf (1 pkt.),

- jaką reprezentację grafu (pokaż ją) wykorzystuje ten algorytm (1 pkt.), pokaż działanie algorytmu zaczynając od węzła A (2 pkt.), wypisz krawędzie drzewa - w kolejności ich dodawania (1 pkt.) Punktacja: 16 <=3,0 19 <=3,5 22<=4,0 25 <=4,5 28<=5,0