ZS/Testy/Test 10

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

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.