37. Test ku skúške

posledná zmena: 16.5.2002

15.5.2002

V 7-prvkovom celočíselnom poli máme tieto čísla:

Doplňte tabuľku, podľa toho, aký bude obsah poľa po skončení volania procedúry vytvor_haldu:

V jednom kroku triedením haldou (heapsort) sa prvok z koreňa dostáva medzi utriedené, posledný prvok haldy sa presunie na jeho miesto (do koreňa) a pole sa minimálnymi zmenami stane opäť haldou (uprac_haldu). Postupne zrealizujete všetky kroky tohto triedenia. Do tabuliek zapíšte výsledky po každom kroku:

					7
				6	7
			5	6	7
		4	5	6	7
	3	4	5	6	7
2	3	4	5	6	7

Nasledujúca metóda vypisuje vrcholy neorientovaného grafu metódou do šírky:

procedure graf.dosirky(v:integer);
var i:integer;
    q:queue;
begin
  q:=queue.Create; q.append(v); visited:=[];
  repeat
    q.serve(v);
    if not (v in visited) then
      begin
        visited:=visited+[v];
        // vypíš hodnotu vrcholu v
        for i:=1 to 9 do
          if jeHrana(v,i) then
            q.append(i);
      end;
  until q.empty;
  q.Free;
end;

DKaždý vrchol okrem svojho čísla (od 1 do 9 - vrcholy v poradí zľava doprava zhora nadol) má aj informáciu: jedno písmeno od A do I.
Metódu dosirky sme zavolali s počiatočným vrcholom A (vrchol číslo 4). Dopíšte do grafu ostatné znaky tak, aby sa vrcholy vypísali v poradí:

    A D E G I C B F H

(vnútorne v dátovej štruktúre platí: 1 má susedov 4,5; 2 má susedov 5,6; 3 má suseda 6; 4 má susedov 1,5,7; 5 má susedov 1,2,4; 6 má susedov 2,3,8,9; 7 má susedov 4,8; 8 má susedov 6,7,9; 9 má susedov 6,8).

Čísla 1..15 sa postupne pridávali do prázdneho binárneho vyhľadávacieho stromu tak, že pre každý vrchol stromu platilo: hĺbka ľavého a pravého podstromu sa líši maximálne o 1 a pritom hĺbka ľavého nebola nikdy väčšia ako hĺbka pravého podstromu. Navrhnite poradie čísel, v akom sa pridávali do stromu.

Koľko listov má lexikografický strom, do ktorého sme vložili všetky slová dĺžky 5 zložené len z písmen {a,b,c}, pričom tieto obsahujú rovnaký počet písmen a aj b?

Nasledujúca procedúra v poli smerníkov na reálne čísla (všetky smerníky sú na začiatku rôzne) uvoľní všetky dynamické premenné (okrem prvého výskytu), ktoré obsahujú rovnaké hodnoty (duplikáty) a presmerníkuje ich na jednu z nich. Žiaľ, v procedúre je niekoľko chýb. Opravte ich.

procedure urob(var a:array of ^real);
var
  i,j:integer;
begin
  for i:=low(a) to high(a) do begin
    j:=i+1;
    repeat inc(j) until (j<=high(a)) and (a[i]=a[j]);
    if j<=high(a) then begin
      dispose(a[j]^); a[j]^:=a[i]^;
    end;
  end;
end;

Zistite koľko existuje rôznych aritmetických stromov, ktoré obsahujú práve tieto 3 rôzne operátory +, -, * a štyri rôzne operandy z množiny {1, 2, 3, 4}.

Nasledujúci program číta kódy (čísla od 1 do 999) a nejaké reťazce a eviduje si to do tabuľky tak, že ak sa nejaký kód vyskytne viackrát, tak nový reťazec pridá pred doterajší. Doplňte chýbajúce časti (smerník p ukazuje na postupnosť znakov, položka d obsahuje momentálnu dĺžku):

procedure kody(var t:TStream);
var
  tab:array[1..999] of record p:pointer; d:integer end;
  s:string;
  k:1..999;
  d:integer;
begin
  for k:=1 to 999 do tab[k].p:=nil;
  while t.Position<t.Size do begin
    t.Read(k,sizeof(k));
    t.Read(d,sizeof(d));
    SetLength(s,d);
    t.Read(s[1],d);
    if .......... then begin
      SetLength(s, ........................);
      Move(........................... ,tab[k].d);
      FreeMem(..............)
    end;
    GetMem(tab[k].p, ...............);
    tab[k].d:=Length(s);
    Move(s[1], ......................);
  end;
end;

Ak vypíšeme všetky hodnoty z binárneho vyhľadávacieho stromu algoritmom postorder, dostaneme takúto postupnosť čísel:

    1,4,6,5,3,8,7,2,11,13,15,14,16,12,10,17,9

Vypíšte postupnosť vrcholov algoritmom preorder.
Z tohto stromu sme vyhodili všetky listy. Vypíšte postupnosť vrcholov tohto stromu algoritmom inorder.

Daná procedúra sort je hlavnou procedúrou quick-sortu, pričom volá pomocnú procedúru rozdel, ktorá ako pivota vyberie prvok s indexom (z+k) div 2 a podľa neho rozdelí prvky poľa. Predpokladajte, že rozdel zachová relatívne poradie prvkov v rozdelených dvoch častiach.

procedure sort(z,k:integer);
var
  pivot:integer;
begin
  if z<k then begin
    write('*');
    rozdel(z,k,pivot);
    sort(z,pivot-1); sort(pivot+1,k);
  end;
end;

Koľko hviezdičiek sa vypíše, ak sme na triedenie zadali 20-prvkové pole čísel s hodnotami postupne od 20 do 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ť.