Záverečný test v letnom semestri 2009/2010
- Pre binárny netypový súbor sme napísali procedúru, ktorá zapíše postupnosť nejakých reťazcov do súboru. Každý reťazec bude v súbore uložený tak, že najprv sa zapíše 4-bajtová dĺžka a za ňou bude obsah reťazca:
|
|
procedure Zapis(Pole: array of string);
var
F: ^file;
S: ^string;
D: ^Integer;
I: Integer;
begin
New(S);
D := @I;
F := file.Create('a.dat');
Rewrite(F^);
for I := 1 to Length(Pole) do
begin
S^ := Pole[I];
D^ := Length(S^);
F.BlockWrite(D, 4);
if D <> 0 then
F.BlockWrite(S, D);
end;
F.CloseFile;
end;
|
- V programe je niekoľko chýb. Opravte ich. Deklarácie lokálnych premenných neopravujte.
- Pre dvojsmerný spájaný zoznam sme vytvorili metódy na vyhodenie prvkov zo zoznamu. Doplňte chýbajúce časti:
|
|
type
TVrchol = class
Prev, Next: TVrchol;
end;
TZoznam = class
Z, K: TVrchol;
procedure Vyhod(V: TVrchol);
procedure Vyhod(V: array of TVrchol);
end;
procedure TZoznam.Vyhod(V: TVrchol);
begin
if V.Prev = nil then
Z := V.Next
else
________________________;
if V.Next = nil then
K := V.Prev
else
_________________________;
V.Free;
end;
procedure TZoznam.Vyhod(V: array of TVrchol);
var
I: Integer;
begin
for I := 0 to High(V) do
_____________________________;
end;
|
- Pre binárny strom sme zadefinovali metódu Urob aj globálnu funkciu Urob:
|
|
type
TStrom = class;
TFunkcia = function (S: TStrom): string;
TStrom = class
Info: Integer;
L, P: TStrom;
function Urob(F: TFunkcia): string;
end;
function TStrom.Urob(F: TFunkcia): string;
begin
if (L = nil) or (P = nil) then
Result := F(Self)
else
Result := L.Urob(F) + F(Self) + P.Urob(F);
end;
function Urob(S: TStrom): string;
begin
if (S.L = nil) and (S.P = nil) then
Result := IntToStr(S.Info)
else
Result := '*';
end;
|
-
- Čo vypíše nasledovné volanie, ak Strom má uvedený tvar:
|
|
WriteLn(Strom.Urob(@Urob));
|
- Do lexikografického stromu (prefixový strom) sme vložili tieto slová:
|
|
pes, pas, pos, posol, osol, sol, eso, pasy, osly, esa, osa,
osy, pel, pol, pal, paly, polo, les, posly, lesy, lese, osla
|
- Koľko všetkých vrcholov a koľko listov bude mať tento strom, ak bol na začiatku úplne prázdny?
- Pre binárny vyhľadávací strom sme zapísali nerekurzívnu metódu na pridávanie novej hodnoty do stromu:
|
|
procedure TBVStrom.Vloz(X: Integer);
var
S: TVrchol;
begin
if Koren = nil then
Koren := TVrchol.Create(X)
else
begin
S := Koren;
while _________________ do
if S.Info > X then
if S.L = nil then
_________________________
else
S := ____________________
else
if S.P = nil then
_________________________
else
S := ____________________;
end;
end;
|
- Doplňte chýbajúce časti riadkov programu.
- Hodnotami operandov aritmetického stromu budú množiny celých čísel. Takto sme upravili definície príslušných tried:
|
|
type
TMnozina = set of Byte;
TAStrom = class
function Hodnota: TMnozina; virtual; abstract;
function Prefix: string; virtual; abstract;
end;
TAOperacia = class(TAStrom)
Op: Char;
L, P: TAStrom;
constructor Create(Z: Char; LL, PP: TAStrom);
function Hodnota: TMnozina; override;
function Prefix: string; override;
end;
TAOperand = class(TAStrom)
Hod: TMnozina;
constructor Create(H: TMnozina);
function Hodnota: TMnozina; override;
function Prefix: string; override;
end;
|
- Zistite, akú hodnotu vráti aritmetický strom (AS.Hodnota), ak jeho AS.Prefix vyzerá nasledovne:
|
|
+ [3 5 7 8] * - [1 2 4 7] [2 3 4 5] [1 5 7 9]
|
- Pomocou triedenia Heap-sort sa bude triediť toto 20 prvkové pole:
| 10
|
9
|
8
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
20
|
19
|
18
|
17
|
16
|
15
|
14
|
13
|
12
|
11
|
- Do prvého riadku nasledujúcej tabuľky vpíšte, ako bude vyzerať halda po prvom kroku algoritmu (VytvorHaldu) a do ďalšieho zapíšte výsledok jedného kroku triedenia (výmena dvoch konkrétnych prvkov a znovu vytvorenie haldy).
- Naprogramovali sme algoritmus triedenia, ktorý usporiada prvky typového binárneho súboru celých čísel. Algoritmus vychádza z MinSortu, ale museli sme ho trochu upraviť:
|
|
type
TSubor = file of Integer;
procedure Sort(var F: TSubor);
var
I, X, Min: Integer;
begin
I := -1;
while I < FileSize(F)-1 do
begin
Reset(F);
while not Eof(F) do
begin
if FilePos(F) < I then
Read(F, X)
else if FilePos(F) = I then
Write(F, Min)
else if FilePos(F) = I + 1 then
Read(F, Min)
else
begin
Read(F, X);
if X < Min then
begin
Seek(F, FilePos(F) - 1);
Write(F, Min);
Min := X;
end;
end;
end;
Inc(I);
end;
end;
|
- Tento algoritmus niekoľkokrát prechádza všetky prvky súboru (vnútorný while-cyklus) a po každom prechode sa niečo v súbore zmení. Na začiatku súbor obsahoval týchto 10 celých čísel:
| 11
|
15
|
19
|
15
|
11
|
13
|
7
|
8
|
9
|
7
|
- Postupne vypíšte obsah všetkých prvkov súboru po každom prechode vnútorného cyklu (tam, kde sa robí Inc(I)):
- Graf sme reprezentovali metódou pole množín susedov. Napísali sme metódu, ktorá o danom grafe zistí, či je orientovaný alebo neorientovaný. Metóda Test má vrátiť True vtedy, keď je graf neorientovaný (každá hrana je definovaná v oboch smeroch):
|
|
type
TGraf = class
G: array [1..N] of set of 1..N;
function Test: Boolean;
end;
function TGraf.Test: Boolean;
var
I, J: Integer;
M: set of 1..N;
begin
Result := True;
for I := 1 to N do
begin
M := [];
for J := 1 to N do
if I in G[J] then
M := _____________________;
Result := __________________________________;
end;
end;
|
- Dopíšte chýbajúce časti riadkov programu.
- Do algoritmu prehľadávania grafu do šírky sme pre neorientovaný graf pridali označovanie prechádzaných vrcholov písmenami abecedy (každý vrchol má pridaný atribút Znak):
|
|
procedure TGraf1.Dosirky(V: Integer);
var
I: Integer;
Z: Char;
Queue: TQueue;
begin
Queue := TQueue.Create;
Queue.Append(V);
Z := 'A';
repeat
Queue.Serve(V);
if not (V in Visited) then
begin
Visited := Visited + [V];
G[V].Znak := Z;
Inc(Z);
for I := 0 to High(G) do
if not (I in Visited) and JeHrana(V, I) then
Queue.Append(I);
end;
until Queue.Empty;
Queue.Free;
end;
|
- Máme daný nasledovný graf so 16 vrcholmi. Tieto sú zoradené v poli G postupne po "riadkoch" zľava doprava (v prvom riadku sú vrcholy s indexmi 0 až 3, v druhom 4 až 7, ...). Algoritmus Dosirky naštartujeme z 9. vrcholu (druhý vrchol v treťom riadku). Zapíšte do každého vrcholu písmeno, ktoré mu pridelí tento algoritmus do šírky.
-
