egz4

Zadania egzaminacyjne z przcdmiolu „Algorytmy i struktury danych*’, I rok l&Z, czerwiec 1996

Zestaw B

I w aga Każde zadanie należy rozwiązać na oddzielnej kartce

Zad. 1 Porównaj cechy struktur danych typu: plik rekordów drzewo rekordów

Zad. 2 Omów strukturę modułu i zasady podziału programu na moduły

.W '

Zad. 3 Omów rodzaje stosów, ich przeznaczenie i zasady obsługi, struktury danych i podstawowi operacje wykonywane na stosie.    -    .........

Zad. 4 Zapisać ideę algorytmu sortowania szybkiego (QuickSort).

V

Zad. 5 Węzeł drzewa BST ma następującą strukturę danych: węzeł = rccord

wart: integer liczn : integer

>    I.p : wsk_wezla

end

Napisz procedurę wartościującą pole liczn w węzłach tak. aby wartością pola liczn dla danego węzła była suma pól wart dla węzłów w obu podrzewach danego węzła.

Zad. 6 TV\ iorcin *^ł?.m*nrouej iab'ieyłwrwttr;    U..9'} wpisać ciąg licz

V-' używając następującej funkcji haszulącej

( 0

hf.N)⁸¹^ h(x div 10)

- l-rh(x div 10) ⁴

oraz kwadratowej metody rozwiązywania kolizji.

dla x*0

dla x parzystych dla x nieparzystych

■

72 j“ 25 20’

^4o7> u-

Zad. 7 b

Napisz procedurę, która rozdzieli elementy źródłowego pliku rekordów na 2 pliki wynikowe. Kolejne serie rekordów z pliku źródłowego, mają być wpisywane do plików* wynikowych naprzemian tzn. kolejne serie nieparzyste do pierwszego pliku, a parzyste do drugiego pliku wynikowego. Serię stanowią kolejne rekordy dla których pole klucz jest uporządkowane rosnąco. Jeżeli wartość klucza w kolejnym rekordzie odczytanym z pliku jest mniejsza niż wartość klucza w poprzednio odczytanym rekordzie, nowy rekord należy już do nowej serii i ma postać wpisany do innego pliku niż rekord poprzedni.: r[i].kłucz.    ___ t o

W

At

A4 hfc)

iujc<?^:

/

07..

C '

l Ad

■> bt

- s

V\ ( 2^

*lo)

ił

0

4    ii

1 'iOi

1

5    iT

r

\

(

bc

/!+    n(U>^

h(/H

frr-tf

r

V.

2' V,(A

I

t.—

ił

h -i	, 1	a. o	s	k(\)	>U hfl)
\ :	•	f	C I J	/i+ ^Mo)	-2f blo

-ti