ZS/Testy/Test 09

Z Pascal
Prejsť na: navigácia, hľadanie

Záverečný test v letnom semestri 2009/2010



  1. 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.


  1. 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;


  1. 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;
LS Test 09 1.png
Čo vypíše nasledovné volanie, ak Strom má uvedený tvar:
WriteLn(Strom.Urob(@Urob));


  1. 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?


  1. 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.


  1. 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]


  1. 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).
 
 


  1. 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)):
 
 
 
 
 
 
 
 
 
 


  1. 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.


  1. 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.
LS Test 09 2.png