egz2

Zestaw 11

Nr indeksu:

ALGORYTMY l STRUKTURY DANYCH - Egzamin

Nazwisko i imię

UWAGA: Każde zadanie musi być rozwiązane na osobnej (podpisanej i opatrzonej numerem zadania i zestaWu) kartce. Zadanie 6 należy rozwiązać na kartce z zadaniami: 1. Scharakteryzuj drzewo AVE (budowa węzła, definicję drzeWa aVE, operacje wykonywane na drzewie i ich złożoność, wątły i zalety w porównaniu z innymi strukturami dany cli. przeznaczenie drzewa) '2 Napisz procedurę, która w pliku elementowymi zawierającym rekordy opisujące osoby, zaktualizuje pole adres w rekordzie osoby o podanym nazwisku.

3. Napisz procedurę, która podzieli prostą, jednokierunkową listę rekordów o początku/w na dwie listy (niszcząc:listę początkową) Do listy pierwszej należy dolącżyć elementy zawierające w polu klucz wartość mniejszą lub równą podanejj Wartości ( k ) , do listy drugiej pozostałe elementy.

4 Napisz podprogram wpisujący każdemu węzłowi (x) binarnego drzewa poszukiwń (l!ST) o korzeniu /, minimalną wartość z poddrzewa, którego korzeniem jest x.

5.    Omów algorytm sortowania HeapSort (cechy stogu, zasadę działania algorytmu, cechy, przydatność do sortowania określonych struktur danych).

6.    Dla danej listy sąsiedztwa grafu rlieskierowanego:

A->B,D B—»A.C.E C-*B.D.E D->A.C.F E->B,C,G F->D,G G -*E.F

a)    narysować ten graf

b)    ponumerować węzły w kolejności ich odwiedzania przy przechodzeniu grafu wszerz

(BSF)    -    ^ •