ZS/Testy/Test 09: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
(Vytvorená stránka „{{Nadpis|Záverečný test v zimnom semestri 2009/2010}} <ol><li value="1">Máme dané pole smerníkov na celé a reálne čísla. Doprogramujte telo cyklu vo funkcii ...“)
 
Riadok 1: Riadok 1:
{{Nadpis|Záverečný test v zimnom semestri 2009/2010}}
+
{{Nadpis|Záverečný test v letnom semestri 2009/2010}}
  
  
<ol><li value="1">Máme dané pole smerníkov na celé a reálne čísla. Doprogramujte telo cyklu vo funkcii '''Priemer''', ak viete, že na nepárnych indexoch poľa sú smerníky na celé čísla a na párnych sú smerníky na reálne čísla. Niektoré prvky poľa môžu byť '''nil''' a vtedy sa nezapočítavajú do priemeru:</li></ol>
+
<ol><li value="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:</li></ol>
 
{{Prog}}
 
{{Prog}}
  type
+
  procedure Zapis(Pole: array of string);
  TPole = array of Pointer;
+
&nbsp;
+
function Priemer(P: TPole): Real;
+
 
  var
 
  var
   I, N: Integer;
+
  F: ^file;
 +
  S: ^string;
 +
  D: ^Integer;
 +
   I: Integer;
 
  begin
 
  begin
   Result := 0;
+
   New(S);
   N := Length(P);
+
  D := @I;
   for I := 0 to High(P) do
+
   F := file.Create('a.dat');
 +
  Rewrite(F^);
 +
   for I := 1 to Length(Pole) do
 
   begin
 
   begin
&nbsp;
+
    S^ := Pole[I];
&nbsp;
+
    D^ := Length(S^);
 +
    F.BlockWrite(D, 4);
 +
    if D <> 0 then
 +
      F.BlockWrite(S, D);
 
   end;
 
   end;
   if N <> 0 then
+
   F.CloseFile;
    Result := Result / N;
+
 
  end;
 
  end;
 
|}
 
|}
 +
:: V programe je niekoľko chýb. Opravte ich. Deklarácie lokálnych premenných neopravujte.
  
  
<ol><li value="2">Dopíšte chýbajúce časti programu tak, aby sa vytvorila takáto trojuholníková štruktúra: prvý riadok má 1 prvok so smerníkom na hodnotou 0, druhý má 2 prvky so smerníkmi na hodnoty 10 a 11, tretí má 3 prvky so smerníkmi na hodnoty 20, 21, 22, atď. až 10 riadok má 10 prvkov so smerníkmi na hodnoty 90, 91, ..., 99:</li></ol>
+
<ol><li value="2">Pre dvojsmerný spájaný zoznam sme vytvorili metódy na vyhodenie prvkov zo zoznamu. Doplňte chýbajúce časti:</li></ol>
 
{{Prog}}
 
{{Prog}}
 +
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
 
  var
  P: array of array of ^Integer;
+
   I: Integer;
   I, J: Integer;
+
 
  begin
 
  begin
  _________________________;
+
   for I := 0 to High(V) do
   for I := 0 to High(P) do
+
     _____________________________;
  begin
+
     _____________________;
+
    for J := 0 to __________ do
+
    begin
+
      ________________;
+
      ___________ := I * 10 + J;
+
    end;
+
  end;
+
 
  end;
 
  end;
 
|}
 
|}
  
  
<ol><li value="3">V infixovom zápise aritmetických výrazov sa operácie s rovnakou prioritou vyhodnocujú zľava doprava. Prepíšte daný výraz do prefixového aj postfixového zápisu:</li></ol>
+
<ol><li value="3">Pre binárny strom sme zadefinovali metódu '''Urob''' aj globálnu funkciu '''Urob''':</li></ol>
::: '''1 + 2 * 3 / 4 * 5 / 6 * 7 / 8 / 9 – 1 / 2 / 3 – 4 / 5 / 6'''
+
:: Výraz neupravujte ani nevyhodnocujte.
+
 
+
 
+
<ol><li value="4">Daná funkcia nejako pracuje s množinami:</li></ol>
+
 
{{Prog}}
 
{{Prog}}
 
  type
 
  type
   TSet = set of Byte;
+
   TStrom = class;
&nbsp;
+
  TFunkcia = function (S: TStrom): string;
function Urob(A: array of TSet): TSet;
+
  TStrom = class
  var
+
    Info: Integer;
  I: Integer;
+
    L, P: TStrom;
 +
    function Urob(F: TFunkcia): string;
 +
  end;
 +
   
 +
function TStrom.Urob(F: TFunkcia): string;
 
  begin
 
  begin
   Result := A[0];
+
   if (L = nil) or (P = nil) then
   for I := 1 to High(A) do
+
    Result := F(Self)
    if I mod 2 = 0 then
+
   else
      Result := Result + A[I]
+
    Result := L.Urob(F) + F(Self) + P.Urob(F);
    else
+
end;
      Result := Result - A[I];
+
 +
function Urob(S: TStrom): string;
 +
begin
 +
  if (S.L = nil) and (S.P = nil) then
 +
    Result := IntToStr(S.Info)
 +
  else
 +
    Result := '*';
 
  end;
 
  end;
 
|}
 
|}
:: Zistite, čo vráti volanie:
+
::: {{Obr|LS_Test_09_1.png}}
::: '''Urob([[1], [5, 8, 9], [2, 4, 6], [], [4, 8, 16], [1, 2, 3]])'''
+
:: Čo vypíše nasledovné volanie, ak '''Strom''' má uvedený tvar:
 +
{{Prog}}
 +
WriteLn(Strom.Urob(@Urob));
 +
|}
  
  
<ol><li value="5">Daná funkcia '''Spoj''' by mala zreťaziť všetky reťazce, ktoré sú v parametri otvorené pole reťazcov. Napr. '''Spoj'''(['abc','xyz','ahoj']) by malo vrátiť reťazec 'abcxyzahoj'. Doplňte vyznačené chýbajúce časti programu (nedopisujte nové premenné ani príkazy). Štandardná procedúra '''Move''' kopíruje z nejakej časti pamäte (prvý parameter), do inej (druhý parameter), kde v treťom parametri je počet kopírovaných bajtov.</li></ol>
+
 
 +
<ol><li value="4">Do lexikografického stromu (prefixový strom) sme vložili tieto slová:</li></ol>
 
{{Prog}}
 
{{Prog}}
  function Spoj(S:___________________________): string;
+
  pes, pas, pos, posol, osol, sol, eso, pasy, osly, esa, osa,  
var
+
  osy, pel, pol, pal, paly, polo, les, posly, lesy, lese, osla
  I, D: Integer;
+
begin
+
  D := 0;
+
  for I := 0 to High(S) do
+
    Inc(D, _____________________);
+
  __________________ Result ________________;
+
  D := 1;
+
  for I := 0 to High(S) do
+
    if S[I] <> {{''}} then
+
    begin
+
      Move(_________________ Result _________________);
+
      Inc(D, ________________);
+
    end;
+
  end;
+
 
|}
 
|}
 +
:: Koľko všetkých vrcholov a koľko listov bude mať tento strom, ak bol na začiatku úplne prázdny?
  
  
<ol><li value="6">Máme danú triedu '''TStack''', ktorá pracuje so znakovým  zásobníkom ('''TPrvok''' = '''Char''') a takúto funkciu:</li></ol>
+
<ol><li value="5">Pre binárny vyhľadávací strom sme zapísali nerekurzívnu metódu na pridávanie novej hodnoty do stromu:</li></ol>
 
{{Prog}}
 
{{Prog}}
  function Test: Boolean;
+
  procedure TBVStrom.Vloz(X: Integer);
 
  var
 
  var
   Zas: TStack;
+
   S: TVrchol;
  Znak: Char;
+
 
  begin
 
  begin
   Zas := TStack.Create;
+
   if Koren = nil then
  Read(Znak);
+
    Koren := TVrchol.Create(X)
   while Znak in ['a', 'b'] do
+
   else
 
   begin
 
   begin
     if _______________ Zas.Top _________ then
+
     S := Koren;
     begin
+
     while _________________ do
       if Znak = 'b' then
+
       if S.Info > X then
         _______________________________;
+
         if S.L = nil then
      Zas.Push(Znak);
+
          _________________________
    end
+
        else
    else
+
          S := ____________________
      __________________________
+
       else
       __________________________
+
        if S.P = nil then
      __________________________;
+
          _________________________
    Read(Znak);
+
        else
 +
          S := ____________________;
 
   end;
 
   end;
  Result := (Znak = #13) ________________;
 
  Zas.Free;
 
 
  end;
 
  end;
 
|}
 
|}
:: Dopíšte chýbajúce časti tak, aby funkcia vrátila '''True''' len vtedy, keď reťazec na vstupe obsahuje presne dvojnásobok písmen '''a''', ako písmen '''b'''. Inak by na vstupe nemali byť iné znaky. Znak #13 označuje koniec riadka. Môžete používať metódu triedy '''TStack Top''', ktorá vráti hodnotu na vrchu zásobníka – z vrchu zásobníka ju ale neodoberie ako '''Pop'''.
+
:: Doplňte chýbajúce časti riadkov programu.
  
  
<ol><li value="7">Táto funkcia kreslí nejakú známu krivku a okrem toho aj niečo počíta:</li></ol>
+
<ol><li value="6">Hodnotami operandov aritmetického stromu budú množiny celých čísel. Takto sme upravili definície príslušných tried:</li></ol>
 
{{Prog}}
 
{{Prog}}
  var
+
  type
   R: TRobot;
+
   TMnozina = set of Byte;
&nbsp;
+
  TAStrom = class
function Kresli(N: Integer): Integer;
+
    function Hodnota: TMnozina; virtual; abstract;
&nbsp;
+
     function Prefix: string; virtual; abstract;
  procedure Otoc(Uhol: Integer);
+
  begin
+
     Inc(Result, Uhol);
+
    R.Lt(Uhol);
+
 
   end;
 
   end;
  &nbsp;
+
   
begin
+
   TAOperacia = class(TAStrom)
   Result := 0;
+
     Op: Char;
  if N > 0 then
+
     L, P: TAStrom;
  begin
+
     constructor Create(Z: Char; LL, PP: TAStrom);
    R.Fd(30);
+
     function Hodnota: TMnozina; override;
     Otoc(40);
+
     function Prefix: string; override;
     Inc(Result, Kresli(N - 1));
+
     Otoc(270);
+
    Inc(Result, Kresli(N - 1));
+
     Otoc(50);
+
     R.Fd(-30);
+
 
   end;
 
   end;
  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:
 +
{{Prog}}
 +
+ [3 5 7 8] * - [1 2 4 7] [2 3 4 5] [1 5 7 9]
 
|}
 
|}
:: Zistite, aké hodnoty vrátia volania:
 
<blockquote>
 
<ol type="a">
 
<li>'''Kresli'''(1)</li>
 
<li>'''Kresli'''(4)</li>
 
<li>'''Kresli'''(10)</li>
 
</ol>
 
</blockquote>
 
  
  
<ol><li value="8">V nasledujúcej časti programu je niekoľko chýb. Textový súbor v každom riadku obsahuje celé číslo od 1 do 30 a za ním je medzera a nejaký reťazec. Program by mal z tohto súboru vypísať tie reťazce, pred ktorými je najčastejšie sa vyskytujúce číslo. Opravte chyby v programe.</li></ol>
+
<ol><li value="7">Pomocou triedenia Heap-sort sa bude triediť toto 20 prvkové pole:</li></ol>
 +
<blockquote><blockquote>
 +
{| border="1"  cellspacing="0"
 +
| width="30" align="center"| 10
 +
| width="30" align="center"| 9
 +
| width="30" align="center"| 8
 +
| width="30" align="center"| 7
 +
| width="30" align="center"| 6
 +
| width="30" align="center"| 5
 +
| width="30" align="center"| 4
 +
| width="30" align="center"| 3
 +
| width="30" align="center"| 2
 +
| width="30" align="center"| 1
 +
| width="30" align="center"| 20
 +
| width="30" align="center"| 19
 +
| width="30" align="center"| 18
 +
| width="30" align="center"| 17
 +
| width="30" align="center"| 16
 +
| width="30" align="center"| 15
 +
| width="30" align="center"| 14
 +
| width="30" align="center"| 13
 +
| width="30" align="center"| 12
 +
| width="30" align="center"| 11
 +
|}
 +
</blockquote></blockquote>
 +
:: 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).
 +
<blockquote><blockquote>
 +
{| border="1"  cellspacing="0"
 +
| width="30" align="center"| &nbsp;
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
| width="30" align="center"|
 +
|-
 +
|| &nbsp; || || || || || || || || || || || || || || || || || || ||
 +
|}
 +
</blockquote></blockquote>
 +
 
 +
 
 +
<ol><li value="8">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ť:</li></ol>
 
{{Prog}}
 
{{Prog}}
 +
type
 +
  TSubor = file of Integer;
 +
 +
procedure Sort(var F: TSubor);
 
  var
 
  var
  P: array [1..30] of Integer;
+
   I, X, Min: Integer;
  T: FileText;
+
   I, M: Integer;
+
  S: string;
+
 
  begin
 
  begin
   AssignText(T, 'subor.txt');
+
   I := -1;
   try
+
   while I < FileSize(F)-1 do
    Reset(T);
+
  begin
    for I := 1 to 30 do
+
     Reset(F);
      P[I] := 0;
+
     while not Eof(F) do
     M := 0;
+
     while Eof(T) do
+
 
     begin
 
     begin
       Read(T, I);
+
       if FilePos(F) < I then
       Inc(P[I]);
+
        Read(F, X)
       if P[M] < P[I] then
+
      else if FilePos(F) = I then
         I := M;
+
        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;
 
     end;
     Rewrite(T);
+
     Inc(I);
    while Eof(T) do
+
    begin
+
      ReadLn(T, M, S);
+
      if I = M then
+
        Memo1.Lines.Append(S)
+
    end;
+
  finally
+
    CloseText(T);
+
 
   end;
 
   end;
 
  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:
 +
<blockquote><blockquote>
 +
{| border="1"  cellspacing="0"
 +
| width="40" align="center"| 11
 +
| width="40" align="center"| 15
 +
| width="40" align="center"| 19
 +
| width="40" align="center"| 15
 +
| width="40" align="center"| 11
 +
| width="40" align="center"| 13
 +
| width="40" align="center"| 7
 +
| width="40" align="center"| 8
 +
| width="40" align="center"| 9
 +
| width="40" align="center"| 7
 +
|}
 +
</blockquote></blockquote>
 +
:: Postupne vypíšte obsah všetkých prvkov súboru po každom prechode vnútorného cyklu (tam, kde sa robí '''Inc(I)'''):
 +
<blockquote><blockquote>
 +
{| border="1"  cellspacing="0"
 +
| width="40" align="center"| &nbsp;
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
| width="40" align="center"|
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|-
 +
| || || || || || || || || ||&nbsp;
 +
|}
 +
</blockquote></blockquote>
  
  
<ol><li value="9">Nasledujúca procedúra nejako spracováva dátovú štruktúru rad ('''TQueue''') v globálnej premennej '''Q''':</li></ol>
+
<ol><li value="9">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):</li></ol>
 
{{Prog}}
 
{{Prog}}
  procedure Spracuj;
+
  type
 +
  TGraf = class
 +
    G: array [1..N] of set of 1..N;
 +
    function Test: Boolean;
 +
  end;
 +
 +
function TGraf.Test: Boolean;
 
  var
 
  var
   I1, I2: Integer;
+
   I, J: Integer;
 +
  M: set of 1..N;
 
  begin
 
  begin
   Q.Append(-1);
+
   Result := True;
   Q.Serve(I1);
+
   for I := 1 to N do
  while I1 > 0 do
+
 
   begin
 
   begin
     Q.Serve(I2);
+
     M := [];
     if I2 > I1 then
+
     for J := 1 to N do
      Q.Append(I2)
+
      if I in G[J] then
    else
+
        M := _____________________;
    begin
+
     Result := __________________________________;
      Q.Append(I1);
+
      I1 := I2;
+
     end;
+
 
   end;
 
   end;
 
  end;
 
  end;
 
|}
 
|}
:: Zistite, aký bude obsah radu po vykonaní procedúry Spracuj, ak jeho počiatočné hodnoty boli:
+
:: Dopíšte chýbajúce časti riadkov programu.
::: '''(8, 5, 20, 4, 9, 13, 2, 3, 5, 12, 1, 3, 5, 13)'''.
+
  
  
<ol><li value="10">Chceli sme zadefinovať triedu na prácu s dynamickým poľom celých čísel. '''Property''' by malo zabezpečiť indexovanie tohto poľa pomocou znakových reťazcov a tiež hodnotou takéhoto prvku poľa ('''property''') by mal byť reťazec. V programe sme urobili niekoľko chýb - opravte ich.</li></ol>
+
<ol><li value="10">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'''):</li></ol>
 
{{Prog}}
 
{{Prog}}
  type
+
  procedure TGraf1.Dosirky(V: Integer);
  TSPole = class
+
  private
+
    FPole: array of Integer;
+
    function GetPole: string; virtual;
+
    procedure SetPole(Hodnota: string); override;
+
  public
+
    property Pole [X: string]: string read GetPole write SetPole;
+
  end;
+
&nbsp;
+
function TSPole.GetPole: string; virtual;
+
 
  var
 
  var
 
   I: Integer;
 
   I: Integer;
 +
  Z: Char;
 +
  Queue: TQueue;
 
  begin
 
  begin
   I := IntToStr(X);
+
   Queue := TQueue.Create;
   if (I < 0) or (I > High(Pole)) then
+
   Queue.Append(V);
    Result := {{''}}
+
  Z := 'A';
   else
+
   repeat
     Result := StrToInt(Pole[I]);
+
     Queue.Serve(V);
end;
+
    if not (V in Visited) then
&nbsp;
+
    begin
procedure TSPole.SetPole(Hodnota: string); override;
+
      Visited := Visited + [V];
var
+
      '''G[V].Znak := Z;'''
  I: Integer;
+
      Inc(Z);
begin
+
      for I := 0 to High(G) do
  I := IntToStr(X);
+
        if not (I in Visited) and JeHrana(V, I) then
  if I >= High(Pole) then
+
          Queue.Append(I);
  begin
+
     end;
    if I > 0 then
+
   until Queue.Empty;
      SetLength(Pole, I + 1);
+
  Queue.Free;
     Pole[I] := Hodnota;
+
   end;
+
 
  end;
 
  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.
 +
::: {{Obr|LS_Test_09_2.png}}

Verzia zo dňa a času 18:26, 19. marec 2013

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;
{{{3}}}
Č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.
{{{3}}}