Bodovanie

rozcvičky	0 - 40
prémia	0 - 5
projekt	0 - 10
test	0 - 15
pri počítači	0 - 30
súčet	0 - 100

Výsledná známka

známka A	90 - 100
známka B	84 - 89
známka C	78 - 83
známka D	72 - 77
známka E	66 - 71
známka Fx	0 - 65

Test ku skúške prebehne v stredu 15.5. od 16:30 v posluchárňach A, B a F1

Termíny praktickej skúšky budú v dňoch 20.5., 29.5., 31.5. a 3.6. vždy od 9:00 v halách H3 a H6

• na skúšku sa prihláste cez webovú stránku Skúšky - prihlasovať sa môžete do 19.5. - po tomto dátume vám bude niektorý termín pridelený ...
• na skúšku môžete prísť už od 7:30 - vtedy máte 90 minút navyše
• môžete používať vlastný ťahák formátu A4
• prvých 15 minút skúšky môžete vzájomne spolupracovať - toto sa týka len tých, ktorí na skúšku prídu súčasne

Preriešte si úlohy z minuloročného testu

(na začiatku každého príkladu uvádzame počet bodov, ktoré sa dali získať za príklad / priemerne získaný počet bodov)

1. (3 / 0.4)  Neorientovaný ohodnotený graf je zadaný tabuľkou susedností. Procedúra back je nejaký algoritmus prehľadávania s návratom na grafe.

var
  g:array['a'..'d','a'..'d'] of byte =
      ((0,1,1,1),(1,0,1,1),(1,1,0,1),(1,1,1,0));
  pocet:integer = 0;

procedure back(v:char);
var
  i:char;
  j:boolean;
begin
  j:=true;
  for i:='a' to 'd' do
    if g[v,i]<>0 then begin
      dec(g[v,i]); dec(g[i,v]); j:=false;
      back(i);
      inc(g[v,i]); inc(g[i,v]);
    end;
  if j then inc(pocet);
end;

Zistite, čo bude v premennej pocet po zavolaní back('a').

2. (3 / 1.1)  Procedúra kopiruj prekopíruje obsah súboru s menom s1 do súboru s menom s2. Pri kopírovaní použije pomocnú pamäť - prístupnú cez smerník buf veľkosti max.

procedure kopiruj(s1,s2:string; max:integer);
var
  t1,t2:TStream;
  buf:pointer;
begin
  t1:=TFileStream.___________________;
  try
    t2:=TFileStream.___________________;
    _________buf__________;
    try
      while t1.Position<t1.Size do
        t2.Write(_________t1.Read__________);
    finally
      _________buf__________;
      t2.___________________;    // zatvoriť
    end;
  finally
    t1.___________________;      // zatvoriť
  end;
end;

Doplňte chýbajúce časti programu.

3. (34/ 0.3)  Zistite, koľko existuje rôznych aritmetických stromov, ktorých inorder je

    1+2+3+4+5+6+7+8

4. (1 / 0.8)  Pre binárny strom nepoznáme hodnoty vo vrcholoch ale vieme, že má tento tvar:

a ak by sme vrcholy vypísali preorderom, dostali by sme vzostupne usporiadanú postupnosť rôznych čísel. Ďalej vieme, že všetky vrcholy, ktoré sú rovnako vzdialené od koreňa, majú svoju číselnú hodnotu zloženú len z rovnakých cifier, napr. samé 5, t.j. 5, 55, 555, 5555, ... Očíslujte strom.

5. (2.5 / 0.1)  Ideu lexikografického stromu využijeme na zistenie frekvenčnej tabuľky z celých čísel, pričom tieto čísla budeme "rozoberať" po bitoch a z tohto sa budeme rozhodovať, kam pokračovať v strome:

type
  TLexStrom = class
    pocet:integer;
    p:array[0..1] of TLexStrom;
    constructor Create;
    procedure pridaj(i:integer);
    function vypis(i,j:integer):string;
  end;

constructor TLexStrom.Create;
begin
  pocet:=0; p[0]:=nil; p[1]:=nil;
end;

procedure TLexStrom.pridaj(i:integer);
begin
  if i=0 then inc(pocet)
  else begin
    if p[i mod 2]=nil then p[i mod 2]:=TLexStrom.Create;
    p[i mod 2].pridaj(i div 2);
  end;
end;

function TLexStrom.vypis(i,j:integer):string;
begin
  if pocet>0 then Result:=IntToStr(i)+','
  else Result:='';
  if p[0]<>nil then Result:=Result+p[0].vypis(i+j,2*j);
  if p[1]<>nil then Result:=Result+p[1].vypis(i,2*j);
end;

...
  l:=TLexStrom.Create;
  for i:=1 to 20 do l.pridaj(i);
  Label1.Caption:=l.vypis(0,1);

V programe je chyba a preto nám výpis nedá správne výsledky.

1. Zistite, čo sa presne vypíše.
2. Opravte chybu.
3. Zistite, čo sa vypíše po oprave chyby.

6. (2.3 / 1.1)  Pred vykonaním procedúry VytvorHaldu vyzerá pole, z ktorého chceme vytvoriť haldu, takto:

1

9

7

8

5

6

3

2

4

Vypíšte obsah poľa po skončení procedúry.

7. (1.7 / 0.9)  Neorientovaný graf je reprezentovaný poľom množín susedov:

type
  TGraf = class
    g:array of set of byte;
    procedure pridajVrchol;
    procedure pridajHranu(i,j:integer);
  end;

procedure TGraf.pridajHranu(i,j:integer);
begin
  if i<>j then begin
    g[i]:=g[i]+[j]; g[j]:=g[j]+[i];
  end;
end;

procedure TGraf.pridajVrchol;
var
  i,j:integer;
begin
  SetLength(g,Length(g)+1);
  i:=high(g); g[i]:=[]; j:=i div 2;
  while j>1 do begin
    pridajHranu(i,j-2);
    j:=j div 2;
  end;
end;

Po zavolaní

  g:=TGraf.Create;
  for i:=1 to 10 do g.pridajVrchol;

sa vytvorí graf s 10 vrcholmi.

1. Nakreslite tento graf.
2. Navrhnite do grafu minimálny počet nových hrán tak, aby sa tento graf stal súvislý.

8. (2.7 / 1.1)  Pomocou triedenia zlučovaním chceme utriediť 10-prvkové pole:

5

15

3

8

1

23

7

3

17

27

Časť algoritmu vyzerá takto:

var
  p:array[1..10] of integer;
  pocet:integer = 0;

procedure mergeSort(z,k:integer);
var
  s:integer;
begin
  inc(pocet);
  if z<k then begin
    s:=(z+k) div 2;
    mergeSort(z,s);
    mergeSort(s+1,k);
    zluc(z,s,k);
  end;
end;

Pomocná procedúra zluc zlúči utriedené časti.
Zistite, koľkokrát sa zavolá táto rekurzívna procedúra mergeSort pre dané pole, ak je prvé volanie mergeSort(1,10) - t.j. zaujíma nás hodnota premennej pocet.

9. (3 / 1.1)  Máme danú postupnosť 16 čísel, ktorú budeme postupne pridávať do binárneho vyhľadávacieho stromu pomocou nasledovného postupu:

var
  p:array[0..15] of integer =
        (17,50,27,77,100,93,73,64,273,237,151,173,13,37,91,71);
  ...
  s:=TBVS.Create;
  i:=0; j:=0;
  while i<16 do begin
    s.vloz(p[i]); s.vloz(p[i+1]); inc(i,2);
    s.zrus(p[j]); inc(j);
  end;

Nakreslite výsledný strom. Predpokladáme, že metóda zrus, keď treba, zamieňa vyhadzovaný vrchol s minimálnym vrcholom z pravého podstromu.

10. (2.7 / 1.1)  Pre jednosmerný spájaný zoznam potrebujeme zadefinovať metódu vsetky, ktorá bude postupne testovať rôzne filtrovacie funkcie a ak je nejaká z nich splnená, tak sa spustí príslušný príkaz. Filter aj príkaz zadeklarujte ako procedurálne typy s jedným parametrom typu TVrchol:

type
  prikaz = _________________________;
  filter = _________________________;
  fprikaz = record f:filter; pr:prikaz; end;

  TZoznam = class
    z,k:TVrchol;
    procedure vsetky(fp:array of fprikaz);
  end;

procedure TZoznam.vsetky(fp:array of fprikaz);
var
  p:TVrchol;
  i:integer;
begin
  p:=z;
  while p<>nil do begin
    for i:=low(fp) to high(fp) do
      if ______________________________________________ then
        _________________________;
    p:=p.next;
  end;
end;

Ak v poli fp je namiesto filtra nil, znamená to, že príslušný príkaz sa má vykonať.

Riešenie príkladu praktickej skúšky z minulého roku

unit UnitGraf;

interface

uses
  Graphics;

const
  max = 1000;

type
  TVrchol = class
    x,y:integer;
    s:array [1..max] of integer;
    visited:boolean;
    constructor Create;
  end;

  TGraf = class
  private
    g:array [1..max] of TVrchol;
    zac,kon:integer;
    cesta,maxcesta:array of integer;
    maxh:real;
    stop:boolean;
    c:TCanvas;
    procedure kresli;
    procedure backtracking(i:integer; h:real);
    procedure ciara(i,j:integer; col:TColor);
  public
    constructor Create(meno:string; cc:TCanvas);
    procedure start;
    procedure zastav;
  end;

implementation

uses
  Classes, SysUtils, Forms;

const
  nie=255;

constructor TVrchol.Create;
var
  i:integer;
begin
  for i:=1 to max do s[i]:=nie;
  visited:=false;
end;

constructor TGraf.Create(meno:string; cc:TCanvas);
var
  t:TStream;
  i,j,k:integer;
begin
  c:=cc;
  t:=TFileStream.Create(meno,fmOpenRead);
  k:=1;
  while t.Position<t.Size do begin
    t.Read(i,4);
    g[i]:=TVrchol.Create;
    if k=1 then zac:=i
    else if k=2 then kon:=i;
    inc(k);
    with g[i] do begin
      t.Read(x,4); t.Read(y,4);
      repeat
        t.Read(j,4); if j<>0 then t.Read(s[j],1);
      until j=0;
    end;
  end;
  t.Free;
  kresli;
end;

procedure TGraf.kresli;
var
  i,j:integer;
begin
  c.Pen.Width:=3;
  for i:=1 to max do
    if g[i]<>nil then
      with g[i] do begin
        for j:=i+1 to max do
          if s[j]<>nie then begin
            ciara(i,j,clDkGray);
            c.TextOut((x+g[j].x)div 2,(y+g[j].y)div 2,IntToStr(s[j])+'%');
          end;
      end;
  c.Pen.Width:=1;
  c.Brush.Color:=clBlue; with g[zac] do c.Ellipse(x-5,y-5,x+5,y+5);
  c.Brush.Color:=clRed;  with g[kon] do c.Ellipse(x-5,y-5,x+5,y+5);
end;

procedure TGraf.start;
var
  i:integer;
begin
  stop:=false; maxh:=0;
  backtracking(zac,1);
  c.Font.Height:=20; c.Brush.Style:=bsClear;
  if maxh=0 then begin
    c.TextOut(0,0,'Riešenie neexistuje')
  end
  else begin
    c.TextOut(0,0,'Bezpečnosť cesty = '+FloatToStr(maxh*100)+'%');
    for i:=0 to high(maxcesta)-1 do
      ciara(maxcesta[i],maxcesta[i+1],clBlue);
  end;
end;

procedure TGraf.ciara(i,j:integer; col:TColor);
begin
  c.Pen.Color:=col;
  with g[i] do c.MoveTo(x,y);
  with g[j] do c.LineTo(x,y);
end;

procedure cakaj(ms:Longint);
var
  potom:TDateTime;
begin
  potom:=Now + EncodeTime(0,ms div 60000,(ms div 1000) mod 60,ms mod 1000);
  while Now < potom do Application.ProcessMessages;
end;

procedure TGraf.backtracking(i:integer; h:real);
var
  j:integer;
begin
  if (h=0) or (h<maxh) then exit;
  g[i].visited:=true; SetLength(cesta,Length(cesta)+1); cesta[high(cesta)]:=i;
  if i=kon then begin
    if h>maxh then begin
      maxh:=h; maxcesta:=cesta;
    end
  end
  else
    for j:=1 to max do
      if (g[j]<>nil) and not g[j].visited and (g[i].s[j]<>nie) then begin
        ciara(i,j,clRed); cakaj(10);
        backtracking(j,h*g[i].s[j]/100);
        ciara(i,j,clDkGray);
        if stop then exit;
      end;
  g[i].visited:=false; SetLength(cesta,Length(cesta)-1);
end;

procedure TGraf.zastav;
begin
  stop:=true;
end;

end.

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls;

type
  TForm1 = class(TForm)
    Image1: TImage;
    Button1: TButton;
    Button2: TButton;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

uses
  UnitGraf;

{$R *.DFM}

var
  g:TGraf;

procedure TForm1.FormCreate(Sender: TObject);
begin
  DoubleBuffered:=true;
  g:=TGraf.Create('bond1.dat',Image1.Canvas);
  Button1.Enabled:=true;
  Button2.Enabled:=false;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  Button1.Enabled:=false;
  Button2.Enabled:=true;
  g.start;
  Button2.Enabled:=false;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  Button2.Enabled:=false;
  g.zastav;
end;

end.