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

Z Pascal
Prejsť na: navigácia, hľadanie
(Vytvorená stránka „{{Nadpis|Záverečný test v zimnom semestri 2010/2011}} <ol><li value="1">Dané funkcie pracujú s množinami:</li></ol> {{Prog}} type TMnozina = set of Byte; &n...“)
 
Riadok 1: Riadok 1:
{{Nadpis|Záverečný test v zimnom semestri 2010/2011}}
+
{{Nadpis|Záverečný test v letnom semestri 2010/2011}}
  
  
<ol><li value="1">Dané funkcie pracujú s množinami:</li></ol>
+
<ol><li value="1">Zadefinovali sme triedu '''TPole''', ktorá "sa tvári" ako jednorozmerné pole čísel, pritom v skutočnosti toto pole uchovávame v údajovom prúde v súbore na disku ('''TStream'''). Opravte chyby v programe:</li></ol>
 
{{Prog}}
 
{{Prog}}
 
  type
 
  type
   TMnozina = set of Byte;
+
   TPole = class
&nbsp;
+
  public
function Rob(P: array of TMnozina): TMnozina;
+
    F: TStream;
var
+
    function Citaj(I: Integer): Integer;
   I: Byte;
+
    procedure Zapis(I, J: Integer);
 +
    function FPocet: Integer;
 +
    procedure Zmen(I: Integer);
 +
   private
 +
    constructor Create(Meno: string);
 +
    destructor Destroy; override;
 +
    property Prvok[I: Integer]: Integer read Citaj write Zapis; default;
 +
    property Pocet: Integer read Zmen write FPocet; // počet prvkov poľa
 +
  end;
 +
 +
implementation
 +
 +
constructor TPole.Create(Meno: string);
 
  begin
 
  begin
   Result := [];
+
   F := TFileStream.Create(Meno, fmCreate);
  for I := 0 to High(P) do
+
    if I mod 2 = 0 then
+
      Result := Result + P[I]
+
    else
+
      Result := Result - P[I];
+
 
  end;
 
  end;
  &nbsp;
+
   
  function Rob(P: array of Byte): TMnozina;
+
  function TPole.Citaj(I: Integer): Integer;
var
+
  I: Byte;
+
 
  begin
 
  begin
   Result := [];
+
   F.Read(Result, 4); F.Position := I;
  for I := 0 to High(P) do
+
end;
    if I mod 2 = 0 then
+
      Result := Result + [P[I]]
+
procedure TPole.Zapis(I, J: Integer);
    else
+
begin
      Result := Result - [P[I]];
+
  F.Position := I; F.Write(J, 4);
 +
end;
 +
 +
function TPole.FPocet: Integer;
 +
begin
 +
  Result := F.Position;
 +
end;
 +
 +
procedure TPole.Zmen(I: Integer);
 +
begin
 +
  F.Position := I;
 +
end;
 +
 +
destructor TPole.Destroy;
 +
begin
 +
  F.Close;
 
  end;
 
  end;
 
|}
 
|}
::Zistite, čo vráti takéto volanie:
 
:::'''Rob([Rob([4, 8, 4, 9]), [4, 5], Rob([[1, 2], [2, 3, 4]])])'''
 
  
  
<ol><li value="2">Funkcia '''Hviezda''' kreslí známu krivku snehová vločka a okrem toho aj niečo počíta:</li></ol>
+
<ol><li value="2">Zistite, koľko existuje rôznych aritmetických stromov, ktorých '''inorder''' je</li></ol>
 
{{Prog}}
 
{{Prog}}
  var
+
  1 + 2 + 3 + 4
  R: TRobot;
+
&nbsp;
+
function Hviezda(N, D, U: Integer): Real;
+
begin
+
  if N = 0 then
+
  begin
+
    Result := D;
+
    Robot.Fd(D);
+
  end
+
  else
+
    Result := Hviezda(N - 1, D div 3, -60) +
+
              Hviezda(N - 1, D div 3, 120) +
+
              Hviezda(N - 1, D div 3, -60) +
+
              Hviezda(N - 1, D div 3, 0);
+
  Robot.Rt(U);
+
end;
+
 
|}
 
|}
::Zistite, aké hodnoty vrátia volania:
+
:: Ľubovoľné 3 z takýchto aritmetických stromov vypíšte '''postorderom'''.
<blockquote>
+
<ol type="a">
+
<li>'''Hviezda(1, 108, 0)'''</li>
+
<li>'''Hviezda(3, 108, 0)'''</li>
+
<li>'''Hviezda(5, 108, 0)'''</li>
+
</ol>
+
</blockquote>
+
  
  
<ol><li value="3">V nasledujúcom programe sa postupne generuje 20 robotov, ktoré kreslia nejaké čiary. Po nejakom čase tento program spadne. Zistite, akú celkovú dráhu tieto roboty stihnú prejsť, kým program nespadne.</li></ol>
+
<ol><li value="3">Pre binárny strom sme zadefinovali konštruktory, pomocou ktorých sa dá prečítať celú štruktúru stromu z binárneho súboru. Súbor obsahuje trojice celých čísel, ktoré popisujú jednotlivé vrcholy: prvé číslo trojice je '''Info''', ďalšie dve čísla (ak sú rôzne od 0) sú číslami viet, kde začína ľavý a pravý sused:</li></ol>
 
{{Prog}}
 
{{Prog}}
 +
type
 +
  TSubor = file of Integer;
 +
  TStrom = class
 +
    Info: Integer;
 +
    L, P: TStrom;
 +
    constructor Create(Meno: string);
 +
    constructor Create(var F: TSubor);
 +
  end;
 +
 +
constructor TStrom.Create(Meno: string);
 
  var
 
  var
   Pole: array [1..20] of TRobot;
+
   F: TSubor;
  I, J, N: integer;
+
 
  begin
 
  begin
   Pole[1] := TRobot.Create;
+
   AssignFile(F, Meno);
   N := 1;
+
  Reset(F);
   while True do
+
  _________________________
 +
  CloseFile(F);
 +
end;
 +
 +
constructor TStrom.Create(var F: TSubor);
 +
var
 +
   LV, PV: Integer;
 +
begin
 +
  Read(F, Info); Read(F, LV); Read(F, PV);
 +
   if LV > 0 then
 
   begin
 
   begin
     Pole[N].Rt(10);
+
     _________________________
    J := N;
+
    for I := 1 to N do
+
    begin
+
      Pole[I].Fd(N);
+
      Inc(J);
+
      Pole[J] := TRobot.Create;
+
    end;
+
    N := J;
+
 
   end;
 
   end;
 +
  if PV > 0 then
 +
  begin
 +
    _________________________
 +
  end;
 +
end;
 
|}
 
|}
  
  
<ol><li value="4">Daná časť programu číta z textového súboru, ktorý obsahuje len celé čísla a niektoré z nich vypisuje:</li></ol>
+
<ol><li value="4">Máme definovanú takúto funkciu '''Urob''':</li></ol>
 
{{Prog}}
 
{{Prog}}
  for I := 1 to 10 do
+
  function Urob(F: array of TFunkcia): Integer;
  begin
+
var
    for J := 1 to I do
+
  I: Integer;
      Read(Subor, K);
+
begin
    WriteLn(K);
+
  Result := 2;
    if I mod 2 = 1 then
+
  for I := 0 to High(F) do
      Readln(Subor)
+
     Result := F[I](Result);
     else
+
end;
      Reset(Subor);
+
  end;
+
 
|}
 
|}
:: Zistite, aké hodnoty sa vypísali, ak vstupný súbor bol takýto:
+
:: ktorá ako parameter dostáva postupnosť funkcií typu '''TFunkcia'''. Predpokladajte, že máme definované tieto tri funkcie (všetky tri typu '''TFunkcia'''), pre ktoré
 +
::* '''Fun1''' vráti svoj parameter vynásobený 3,
 +
::* '''Fun2''' vráti svoj parameter znížený o 10,
 +
::* '''Fun3''' vráti svoj parameter celočíselne vydelený 10.
 +
:: S akými parametrami treba zavolať funkciu '''Urob''', aby jej výsledkom bola hodnota '''11'''.
 
{{Prog}}
 
{{Prog}}
  1 2 3
+
  Urob(_________________________________________________________)
4 5 6 7
+
8 9 10 11 12
+
13 14 15 16 17 18
+
19 20 21 22 23 24 25
+
 
|}
 
|}
  
  
<ol><li value="5">Zistite, ktoré prvky bude obsahovať množina '''M''' na konci tohto programu:</li></ol>
+
<ol><li value="5">Pomocou triedenia Heap-sort sa bude triediť toto 20 prvkové pole:</li></ol>
 +
<blockquote><blockquote>
 +
{| border="1"  cellspacing="0"
 +
| width="30" align="center"| 11
 +
| width="30" align="center"| 12
 +
| width="30" align="center"| 13
 +
| width="30" align="center"| 14
 +
| width="30" align="center"| 15
 +
| width="30" align="center"| 16
 +
| width="30" align="center"| 17
 +
| width="30" align="center"| 18
 +
| width="30" align="center"| 19
 +
| width="30" align="center"| 20
 +
| width="30" align="center"| 1
 +
| width="30" align="center"| 2
 +
| width="30" align="center"| 3
 +
| width="30" align="center"| 4
 +
| width="30" align="center"| 5
 +
| width="30" align="center"| 6
 +
| width="30" align="center"| 7
 +
| width="30" align="center"| 8
 +
| width="30" align="center"| 9
 +
| width="30" align="center"| 10
 +
|}
 +
</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="6">Pre lexikografický strom (prefixový strom) máme definovanú jedinú metódu '''Urob''', ktorá do stromu vkladá informácie podľa jedného riadku otvoreného textového súboru:</li></ol>
 
{{Prog}}
 
{{Prog}}
 
  type
 
  type
   TVymenovany = (a, b, c, d, e, f, g);
+
   TVrchol = class
 +
    S: array ['a'..'e'] of TVrchol;
 +
  end;
 +
 +
  TLexStrom = class
 +
    Koren: TVrchol;
 +
    procedure Urob(var F: TextFile; var P: TVrchol);
 +
  end;
 +
 +
procedure TLexStrom.Urob(var F: TextFile; var P: TVrchol);
 
  var
 
  var
   M: set of TVymenovany;
+
   C: Char;
  I: integer;
+
  J: TVymenovany;
+
 
  begin
 
  begin
   M := [];
+
   if P = nil then
   for I := 100 to 150 do
+
    P := TVrchol.Create;
 +
   if not Eoln(F) then
 
   begin
 
   begin
     J := TVymenovany(I mod (Ord(High(TVymenovany)) + 1));
+
     Read(F, C);
     if J in M then
+
     if C = ' ' then
       M := M - [J]
+
       Urob(F, Koren)
 
     else
 
     else
       M := M + [J];
+
       Urob(F, P.S[C]);
 
   end;
 
   end;
 +
end;
 
|}
 
|}
 
+
:: Súbor obsahuje riadok: '''dada da ede a eda da dade'''. Pre objekt '''Strom''' triedy '''TLexStrom''' volanie:
 
+
<ol><li value="6">Aritmetické výrazy sme doplnili o operáciu priradenia ''':=''' (prvý operand musí byť meno premennej a táto operácia priradí druhý operand do tejto premennej - výsledkom operácie je priraďovaná hodnota) a operáciu celočíselného de-lenia '''div''':</li></ol>
+
:::'''- div * - := c + := a 7 2 3 + := b 4 3 5 div * c b a'''
+
:: Prepíšte tento '''prefix''' do '''postfixu''' a tiež zistite jeho hodnotu. Napr. infixový zápis '''((a := 3) + a)''' by mal hodnotu 6. Ak sa vo výraze pri vyhodnocovaní vyskytne nedefinovaná premenná, tak tato ma hodnotu 0.
+
 
+
 
+
<ol><li value="7">Máme danú triedu '''TStack''', ktorá vie pracovať s celočíselným  zásobníkom (TPrvok = Integer) a takúto časť programu:</li></ol>
+
 
{{Prog}}
 
{{Prog}}
  while not Stack.Empty do
+
Strom := TLexStrom.Create;
  begin
+
Strom.Urob(F, Strom.Koren);
    Stack.Pop(I);
+
    if (I mod 5 > 2) or Stack.Empty then
+
      Write(I, ', ')
+
    else
+
    begin
+
      Stack.Pop(J);
+
      Write(J, ', ');
+
      Write(I, ', ');
+
    end;
+
  end;
+
 
|}
 
|}
:: Zistite, čo sa nachádzalo v zásobníku pred cyklom, keď sme dostali takýto výstup:
+
:: vytvorí stromovú štruktúru, v ktorej sú nilové aj nenilové hodnoty (prvky poľa '''S'''). Zistite, koľko je tam dokopy všetkých hodnôt '''nil'''. Uvedomte si, že strom je stupňa 5.
::: '''5, 7, 4, 3, 5, 6, 4, 6, 5, 5,'''
+
:: Pôvodný obsah zásobníka uveďte v poradí od najspodnejšieho prvku až po vrch zásobníka.
+
  
  
<ol><li value="8">Chceli sme zadefinovať triedu na prácu so znakovým zásobníkom, ale urobili sme niekoľko chýb - opravte ich. Do zásobníka vkladáme znaky na začiatok reťazca znakov (zásobníka) a vyberáme ich zo začiatku.</li></ol>
+
<ol><li value="7">Do 20-prvkového poľa sme pomocou hašovacej tabuľky postupne vložili (pomocou procedúry '''Pridaj''') týchto 14 čísel:<br />'''23, 42, 47, 50, 55, 60, 66, 67, 76, 82, 83, 87, 92, 98'''.</li></ol>
 
{{Prog}}
 
{{Prog}}
  type
+
  var
   TStack = class
+
   Pole: array [0..19] of Integer;
    Pole: string;
+
   
    procedure Push(var Z: Char); virtual;
+
  function Hash(Cislo: Integer): Integer;
    procedure Pop(Z: Char); override;
+
    function Empty: Boolean;
+
  end;
+
  &nbsp;
+
  procedure TStack.Push(var Z: Char);
+
 
  begin
 
  begin
   inherited;
+
   Result := Cislo mod Length(Pole);
  Insert(Z, Pole);
+
 
  end;
 
  end;
  &nbsp;
+
   
  procedure TStack.Pop(Z: Char);
+
  procedure Pridaj(Cislo: Integer);
 +
var
 +
  I: Integer;
 
  begin
 
  begin
   if Empty then
+
   I := Hash(Cislo);
    except Exception.Create('zla operacia Pop');
+
   while Pole[I] <> 0 do
   Z := Copy(Pole, 1, 1);
+
    I := (I + 3) mod Length(Pole);
  Delete(Pole, 1);
+
   Pole[I] := Cislo;
end;
+
&nbsp;
+
function TStack.Empty: Boolean;
+
begin
+
   Result := Pole[1] = {{''}};
+
 
  end;
 
  end;
 
|}
 
|}
 +
:: Zistite, ako bude vyzerať výsledné pole (pôvodne v ňom boli samé 0) a koľko kolízií vznikne počas vkladania prvkov.
 +
<blockquote><blockquote>
 +
{| border="0"  cellspacing="0"
 +
| width="30" align="center"| 0
 +
| width="30" align="center"| 1
 +
| width="30" align="center"| 2
 +
| width="30" align="center"| 3
 +
| width="30" align="center"| 4
 +
| width="30" align="center"| 5
 +
| width="30" align="center"| 6
 +
| width="30" align="center"| 7
 +
| width="30" align="center"| 8
 +
| width="30" align="center"| 9
 +
| width="30" align="center"| 10
 +
| width="30" align="center"| 11
 +
| width="30" align="center"| 12
 +
| width="30" align="center"| 13
 +
| width="30" align="center"| 14
 +
| width="30" align="center"| 15
 +
| width="30" align="center"| 16
 +
| width="30" align="center"| 17
 +
| width="30" align="center"| 18
 +
| width="30" align="center"| 19
 +
|}
 +
{| 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"|
 +
|}
 +
</blockquote></blockquote>
  
  
<ol><li value="9">Do poľa smerníkov chceme prečítať riadky textového súboru. Každý smerník bude odkazovať do dynamickej pamäte na postupnosť znakov jedného riadka súboru.  Na koniec každého takéhoto riadka pridáme ešte aj znak '#'. Program na záver vypíše prečítané riadky súboru (aj s ukončovacími znakmi '#'). Doprogramujte chýbajúce časti programu. Š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="8"> Máme trochu pozmenený algoritmus triedenia quick-sort:</li></ol>
 
{{Prog}}
 
{{Prog}}
 +
procedure QuickSort(Zac, Kon: Integer);
 
  var
 
  var
  Pole: array of Pointer;
+
   I, J, Pivot: Integer;
   I: Integer;
+
  S: string;
+
  T: TextFile;
+
 
  begin
 
  begin
   AssignFile(T, 'text.txt');
+
   I := Zac; J := Kon;
   Reset(T);
+
   Pivot := Pole[(Zac + Kon) div 2];
   while not Eof(T) do
+
   repeat
  begin
+
    while (I < Kon) and (Pole[I] < Pivot) do I := I + 1;
    ReadLn(T, S);
+
     while (J > Zac) and (Pivot < Pole[J]) do J := J - 1;
    S := S + '#';
+
     if I <= J then
     SetLength(Pole, Length(Pole) + 1);
+
     begin
     GetMem(___________________________________);
+
      if I < J then Vymen(I, J);
     Move(_____________________________________);
+
      I := I + 1;
  end;
+
      J := J - 1
   CloseFile(T);
+
    end
   for I := 0 to High(Pole) do
+
  until I > J;
    WriteLn(__________________________________);
+
   if J > Zac then QuickSort(Zac, J);
 +
   if I < Kon then QuickSort(I, Kon)
 +
end;
 
|}
 
|}
 +
:: Zistite, ako bude vyzerať obsah poľa tesne po cykle '''repeat''', ešte pred rekurzívnymi volaniami – výsledné pole zapíšte do druhého riadka tabuľky. Vyznačte v poli aj pozíciu pivota.
 +
<blockquote><blockquote>
 +
{| border="1"  cellspacing="0"
 +
| width="30" align="center"| 36
 +
| width="30" align="center"| 93
 +
| width="30" align="center"| 5
 +
| width="30" align="center"| 16
 +
| width="30" align="center"| 96
 +
| width="30" align="center"| 84
 +
| width="30" align="center"| 22
 +
| width="30" align="center"| 62
 +
| width="30" align="center"| 92
 +
| width="30" align="center"| 56
 +
| width="30" align="center"| 21
 +
| width="30" align="center"| 63
 +
| width="30" align="center"| 74
 +
| width="30" align="center"| 5
 +
| width="30" align="center"| 71
 +
| width="30" align="center"| 4
 +
| width="30" align="center"| 3
 +
| width="30" align="center"| 68
 +
| width="30" align="center"| 34
 +
| width="30" align="center"| 1
 +
|-
 +
|| &nbsp; || || || || || || || || || || || || || || || || || || ||
 +
|}
 +
</blockquote></blockquote>
  
  
<ol><li value="10">Dopíšte chýbajúce časti programu tak, aby sa v dynamickom poli '''A''' vytvorila takáto trojuholníková štruktúra: prvý riadok má 1 prvok so smerníkom na prvý prvok poľa '''Pole''', druhý má 2 prvky so smerníkmi na druhý a tretí prvok poľa '''Pole''', tretí má 3 prvky so smerníkmi na ďalšie tri prvky poľa '''Pole''', atď. až 10 riadok má 10 prvkov so smerníkmi na prvky poľa '''Pole''':</li></ol>
+
<ol><li value="9">Neorientovaný graf je reprezentovaný poľom susedov, pričom platí:</li></ol>
 
{{Prog}}
 
{{Prog}}
 +
G[0] = [4]      G[1] = [6, 7]  G[2] = [8]      G[3] = [11]
 +
G[4] = [0, 10]  G[5] = [6, 7]  G[6] = [1, 5]  G[7] = [1, 5]
 +
G[8] = [2]      G[9] = []      G[10] = [4]    G[11] = [3]
 +
|}
 +
:: Zistite počet komponentov grafu a pre každý z nich počet vrcholov.
 +
 +
 +
<ol><li value="10">V tabuľke '''Tab''' evidujeme pre rôzne kódy (číslo od 1 do 999) nejaké znakové reťazce. V položke '''P''' sa nachádza smerník do pamäte, kde začína samotný reťazec a v položke '''D''' bude momentálna dĺžka samotného reťazca. Procedúra '''Pridaj''' prečíta z otvoreného údajového prúdu dvojicu kód a reťazec a pridá ich do tabuľky tak, že ak sa už pre daný kód v tabuľke nejaký reťazec nachádza, tak starý reťazec vyhodí a nahradí ho novým. V súbore sa nachádza najprv kód, za ním nenulová dĺžka reťazca a samotná postupnosť znakov. Doplňte chýbajúce časti.</li></ol>
 +
{{Prog}}
 +
type
 +
  TTabulka = array [1..999] of record P: Pointer; D: Integer; end;
 +
 +
procedure Pridaj(var T: TStream; var Tab: TTabulka);
 
  var
 
  var
   Pole: array [1..1000] of Integer;
+
   S: string;
   P: ^Integer;
+
   Kod, Dlzka: Integer;
  A: array of array of Pointer;
+
  I, J: Integer;
+
 
  begin
 
  begin
   P := ________________________;
+
   T.Read(Kod, SizeOf(Kod));
   SetLength(__________________);
+
   T.Read(Dlzka, SizeOf(Dlzka));
   for I := 0 to High(A) do
+
   SetLength(S, Dlzka);
   begin
+
   T.Read(__________________);
    SetLength(__________________);
+
  if _______________ then
    for J := 0 to ______________ do
+
     FreeMem(___________________);
     begin
+
  GetMem(Tab[Kod].P, ______________________);
      A[I, J] := P;
+
  Tab[Kod].D := Dlzka;
      __________________;
+
  Move(S[1], ______________________);
    end;
+
end;
  end;
+
 
|}
 
|}
 +
:: Uvedomte si, že procedúra '''Move''' kopíruje časť pamäte: z prvého parametra presunie do druhého počet bajtov určených tretím parametrom.

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

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



  1. Zadefinovali sme triedu TPole, ktorá "sa tvári" ako jednorozmerné pole čísel, pritom v skutočnosti toto pole uchovávame v údajovom prúde v súbore na disku (TStream). Opravte chyby v programe:
type
  TPole = class
  public
    F: TStream;
    function Citaj(I: Integer): Integer;
    procedure Zapis(I, J: Integer);
    function FPocet: Integer;
    procedure Zmen(I: Integer);
  private
    constructor Create(Meno: string);
    destructor Destroy; override;
    property Prvok[I: Integer]: Integer read Citaj write Zapis; default;
    property Pocet: Integer read Zmen write FPocet; // počet prvkov poľa
  end;

implementation

constructor TPole.Create(Meno: string);
begin
  F := TFileStream.Create(Meno, fmCreate);
end;

function TPole.Citaj(I: Integer): Integer;
begin
  F.Read(Result, 4); F.Position := I;
end;

procedure TPole.Zapis(I, J: Integer);
begin
  F.Position := I; F.Write(J, 4);
end;

function TPole.FPocet: Integer;
begin
  Result := F.Position;
end;

procedure TPole.Zmen(I: Integer);
begin
  F.Position := I;
end;

destructor TPole.Destroy;
begin
  F.Close;
end;


  1. Zistite, koľko existuje rôznych aritmetických stromov, ktorých inorder je
1 + 2 + 3 + 4
Ľubovoľné 3 z takýchto aritmetických stromov vypíšte postorderom.


  1. Pre binárny strom sme zadefinovali konštruktory, pomocou ktorých sa dá prečítať celú štruktúru stromu z binárneho súboru. Súbor obsahuje trojice celých čísel, ktoré popisujú jednotlivé vrcholy: prvé číslo trojice je Info, ďalšie dve čísla (ak sú rôzne od 0) sú číslami viet, kde začína ľavý a pravý sused:
type
  TSubor = file of Integer;
  TStrom = class
    Info: Integer;
    L, P: TStrom;
    constructor Create(Meno: string);
    constructor Create(var F: TSubor);
  end;

constructor TStrom.Create(Meno: string);
var
  F: TSubor;
begin
  AssignFile(F, Meno);
  Reset(F);
  _________________________
  CloseFile(F);
end;

constructor TStrom.Create(var F: TSubor);
var
  LV, PV: Integer;
begin
  Read(F, Info); Read(F, LV); Read(F, PV);
  if LV > 0 then
  begin
    _________________________
  end;
  if PV > 0 then
  begin
    _________________________
  end;
end;


  1. Máme definovanú takúto funkciu Urob:
function Urob(F: array of TFunkcia): Integer;
var
  I: Integer;
begin
  Result := 2;
  for I := 0 to High(F) do
    Result := F[I](Result);
end;
ktorá ako parameter dostáva postupnosť funkcií typu TFunkcia. Predpokladajte, že máme definované tieto tri funkcie (všetky tri typu TFunkcia), pre ktoré
  • Fun1 vráti svoj parameter vynásobený 3,
  • Fun2 vráti svoj parameter znížený o 10,
  • Fun3 vráti svoj parameter celočíselne vydelený 10.
S akými parametrami treba zavolať funkciu Urob, aby jej výsledkom bola hodnota 11.
Urob(_________________________________________________________)


  1. Pomocou triedenia Heap-sort sa bude triediť toto 20 prvkové pole:
11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10
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. Pre lexikografický strom (prefixový strom) máme definovanú jedinú metódu Urob, ktorá do stromu vkladá informácie podľa jedného riadku otvoreného textového súboru:
type
  TVrchol = class
    S: array ['a'..'e'] of TVrchol;
  end;

  TLexStrom = class
    Koren: TVrchol;
    procedure Urob(var F: TextFile; var P: TVrchol);
  end;

procedure TLexStrom.Urob(var F: TextFile; var P: TVrchol);
var
  C: Char;
begin
  if P = nil then
    P := TVrchol.Create;
  if not Eoln(F) then
  begin
    Read(F, C);
    if C = ' ' then
      Urob(F, Koren)
    else
      Urob(F, P.S[C]);
  end;
end;
Súbor obsahuje riadok: dada da ede a eda da dade. Pre objekt Strom triedy TLexStrom volanie:
Strom := TLexStrom.Create;
Strom.Urob(F, Strom.Koren);
vytvorí stromovú štruktúru, v ktorej sú nilové aj nenilové hodnoty (prvky poľa S). Zistite, koľko je tam dokopy všetkých hodnôt nil. Uvedomte si, že strom je stupňa 5.


  1. Do 20-prvkového poľa sme pomocou hašovacej tabuľky postupne vložili (pomocou procedúry Pridaj) týchto 14 čísel:
    23, 42, 47, 50, 55, 60, 66, 67, 76, 82, 83, 87, 92, 98.
var
  Pole: array [0..19] of Integer;

function Hash(Cislo: Integer): Integer;
begin
  Result := Cislo mod Length(Pole);
end;

procedure Pridaj(Cislo: Integer);
var
  I: Integer;
begin
  I := Hash(Cislo);
  while Pole[I] <> 0 do
    I := (I + 3) mod Length(Pole);
  Pole[I] := Cislo;
end;
Zistite, ako bude vyzerať výsledné pole (pôvodne v ňom boli samé 0) a koľko kolízií vznikne počas vkladania prvkov.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
 


  1. Máme trochu pozmenený algoritmus triedenia quick-sort:
procedure QuickSort(Zac, Kon: Integer);
var
  I, J, Pivot: Integer;
begin
  I := Zac; J := Kon;
  Pivot := Pole[(Zac + Kon) div 2];
  repeat
    while (I < Kon) and (Pole[I] < Pivot) do I := I + 1;
    while (J > Zac) and (Pivot < Pole[J]) do J := J - 1;
    if I <= J then
    begin
      if I < J then Vymen(I, J);
      I := I + 1;
      J := J - 1
    end
  until I > J;
  if J > Zac then QuickSort(Zac, J);
  if I < Kon then QuickSort(I, Kon)
end;
Zistite, ako bude vyzerať obsah poľa tesne po cykle repeat, ešte pred rekurzívnymi volaniami – výsledné pole zapíšte do druhého riadka tabuľky. Vyznačte v poli aj pozíciu pivota.
36 93 5 16 96 84 22 62 92 56 21 63 74 5 71 4 3 68 34 1
 


  1. Neorientovaný graf je reprezentovaný poľom susedov, pričom platí:
G[0] = [4]       G[1] = [6, 7]   G[2] = [8]      G[3] = [11]
G[4] = [0, 10]   G[5] = [6, 7]   G[6] = [1, 5]   G[7] = [1, 5]
G[8] = [2]       G[9] = []       G[10] = [4]     G[11] = [3]
Zistite počet komponentov grafu a pre každý z nich počet vrcholov.


  1. V tabuľke Tab evidujeme pre rôzne kódy (číslo od 1 do 999) nejaké znakové reťazce. V položke P sa nachádza smerník do pamäte, kde začína samotný reťazec a v položke D bude momentálna dĺžka samotného reťazca. Procedúra Pridaj prečíta z otvoreného údajového prúdu dvojicu kód a reťazec a pridá ich do tabuľky tak, že ak sa už pre daný kód v tabuľke nejaký reťazec nachádza, tak starý reťazec vyhodí a nahradí ho novým. V súbore sa nachádza najprv kód, za ním nenulová dĺžka reťazca a samotná postupnosť znakov. Doplňte chýbajúce časti.
type
  TTabulka = array [1..999] of record P: Pointer; D: Integer; end;

procedure Pridaj(var T: TStream; var Tab: TTabulka);
var
  S: string;
  Kod, Dlzka: Integer;
begin
  T.Read(Kod, SizeOf(Kod));
  T.Read(Dlzka, SizeOf(Dlzka));
  SetLength(S, Dlzka);
  T.Read(__________________);
  if _______________ then
    FreeMem(___________________);
  GetMem(Tab[Kod].P, ______________________);
  Tab[Kod].D := Dlzka;
  Move(S[1], ______________________);
end;
Uvedomte si, že procedúra Move kopíruje časť pamäte: z prvého parametra presunie do druhého počet bajtov určených tretím parametrom.