Test z programovania zo šk. roku 1997/98 Predchádzajúca prednáška: Ukážky backtrackingu na grafochZoznam prednášok
28. apr.1999

Bodovanie

1 2 3 4 5 6 7 8 9 10 súčet
max. 3.5 0.5 3.3 3.5 1.6 3.0 0.6 3.0 0.5 3.0 22.5
priemer 0.9 0.4 0.5 1.0 1.0 1.0 0.5 1.1 0.5 1.0 7.5

 

1. V 17 prvkovom celočíselnom poli máme uloženú haldu:

    33 29 30 25 21 27 22 19 24 10 13 17 20 15 18 14 16

    V jednom kroku triedením haldou (heapsort) sa prvok z koreňa dostáva medzi utriedené, posledný prvok haldy sa presunie na jeho miesto a pole sa minimálnymi zmenami stane opäť haldou. Zrealizujete tento jeden krok. Do nasledovných dvoch tabuliek zapíšte výsledok po prvom a druhom kroku triedenia:
     
                                     
     
                                     

2. Daný je aritmetický výraz zapísaný v postfixovom tvare:
      5 2 3 + * 3 7 – 2 + 2 / -
    Nakreslite zodpovedajúci aritmetický strom (vo vnútorných vrcholoch sú operácie, v listoch operandy).
     
3. Všeobecné zoznamy sú definované dátovou štruktúrou:
    type tAtom=char;
         vzoz=^vrchol;
         vrchol=record
           case typ:(at,zoz) of
             at: (hod:tAtom);
             zoz:(syn,dalsi:vzoz);
         end;     Nasledovná procedúra zmen ich modifikuje: procedure zmen(z:vzoz);
    var p:vzoz;
    begin
      if (z<>nil) and (z^.typ=zoz) then
        if z^.dalsi=nil then zmen(z^.syn)
        else
          begin
            p:=z^.syn; z^.syn:=z^.dalsi^.syn; z^.dalsi^.syn:=p;
            zmen(z^.syn); zmen(z^.dalsi^.dalsi);
          end
    end;


    a) Napíšte, ako sa zmení vstupný všeobecný zoznam

    (a(b c)(d(e f))(g(h(i j)))) b) Zapíšte vstupný zoznam z, ak po spracovaní procedúrou zmen má tvar: ((t e s t)z(p a s(c a l u))) Zoznamy vypisujte v textovom tvare.
     
4. Procedúra pridaj pridáva vrcholy do 3-árneho stromu podobným spôsobom ako sa to robí v lexikografickom strome:
    type strom=^vrchol;
         vrchol=record
           info:word;
           syn:array[0..2] of strom
         end;

    procedure pridaj(var s:strom; x,y:word);
    begin
      if s=nil then
        begin
          new(s); s^.info:=0;
          s^.syn[0]:=nil; s^.syn[1]:=nil; s^.syn[2]:=nil;
        end;
      if x=0 then s^.info:=y
      else pridaj(s^.syn[x mod 3],x div 3,y)
    end;

     Ďalej sú dané deklarácie a časť programu: var s:strom;
        i:word;
    begin
      s:=nil; for i:=1 to N do pridaj(s,i,i);


    a) Nakreslite strom pre N=8.

    b) Koľko všetkých a nenulových vrcholov má strom pre N=81?

    c) Aká je hĺbka stromu pre N=250?


5. Binárny vyhľadávací strom vznikol postupným pridávaním vrcholov (začali sme od prázdneho stromu) v tomto poradí:

13 22 16 6 19 9 2 20 7 8 5 1 17 11 4
a) Nakreslite tento strom.

b) Navrhnite čo najviac rôznych čísel (rôznych aj od čísel v strome), ktoré, keby sme pridali do daného stromu (štandardným algoritmom na pridanie vrchola do BVS), tak by sa zakaždým zväčšila jeho hĺbka.


6. Daná je nasledovná deklarácia neorientovaného grafu a procedúra prehľadávajúca graf do hĺbky:

    const n=9;
          graf:array[1..n] of set of 1..n =
            ([3,4,6],[3],[1,2,7,9],[1,5],[4],[1,7],[3,6,8],[7,9],[3,8]);

    var vis:set of 1..n; { množina navštívených vrcholov, na začiatku [] }

    procedure dohlbky(i:integer);
    var j:integer;
    begin
      vis:=vis+[i]; write(i,' ');
      for j:=1 to n do
        if not (j in vis) and (j in graf[i]) then
          dohlbky(j);
    end;

    Zistite, akým vrcholom muselo začínať prehľadávanie do hĺbky, keď skončilo vo vrchole 8. Napíšte túto postupnosť navštevovaných vrcholov.
     
     

7. Daná je postupnosť slov:
    mama ma emu a ema ma mamu umme mume amme meme

    Nakreslite príslušný lexikografický strom pre abecedu {a, e, m, u} (na hrany stromu zapíšte príslušné písmeno, do vrcholov počet výskytov príslušného podreťazca).
     
     

8. Daný program metódou prehľadávania so spätným návratom (backtracking) hľadá nejaké cesty v obĺžnikovej štvorcovej sieti NxM: const N=...; M=...;
var a:array[1..N,1..M] of byte;
    p:integer;

procedure back(i,j:integer);
begin
  if (i=N) and (j=M) then inc(p)
  else if (i in [1..N]) and (j in [1..M]) and (a[i,j]=0) then
    begin
      a[i,j]:=1;
      back(i-1,j);
      back(i+1,j);
      back(i,j+1);
      a[i,j]:=0;
    end;
end;

begin
  fillchar(a,N*M,0); a[2,3]:=1; p:=0;
  back(1,1);
  writeln(p);
end.

 a) Zistite, čo vypíše pre N=3 a M=4.
b) Zistite, čo vypíše pre N=3 a M=5.


9. Daný je binárny strom tohoto tvaru:

    Vo vrcholoch tohoto stromu boli zapísané znaky (type prvok=char), pričom po výpise hodnôt algoritmom POSTORDER sa vypísala postupnosť: s k u s k a z p r o g r a m o v a n i a Zapíšte tieto znaky na správne miesta do daného tvaru stromu.
10. Pre všeobecné stromy (reprezentované nasledujúcou štruktúrou) je definovaná funkcia x:
    type strom=^vrchol;
         vrchol=record
           info:word;
           syn,brat:strom
         end;

    function x(s:strom):word;
    begin
      if s=nil then x:=0
      else x:=max(x(s^.syn)+s^.info,x(s^.brat));
    end;


    a) Zistite, aký výsledok vráti pre daný strom.
    b) Z ktorého vrcholu stromu treba začať (pre ktorý podstrom), aby bol výsledok maximálny?
    c) V strome opravte jeden vrchol (číselnú hodnotu) tak, aby výsledok funkcie pre celý strom bol 41.