Программирование на языке Pascal - тест 12

Упражнение 1:

---

Номер 1

Какую высоту будет иметь дерево синтаксического анализа для выраженияx*(a+b*c–g)+((m-n)*t*d/(s-y))*z

Ответ:

---

Номер 2

Какую высоту будет иметь дерево синтаксического анализа для выражения(a-b)*(c+(x-y)/d)+(k*m-(n/s+t))

Ответ:

---

Номер 3

Какую высоту будет иметь дерево синтаксического анализа для выражения(a+b)*(c*d-k)-((m+n)/s*(t+y)*(z-x))

Ответ:

---

Упражнение 2:

---

Номер 1

Постройте дерево бинарного поиска (дерево сортировки) для входной последовательности чисел 7 2 5 1 8 3 6 4 9 13 11 10 12, а затем распечатайте вершины этого дерева в порядке обратного обхода. Какая последовательность чисел получится

Ответ:

---

Номер 2

Постройте дерево бинарного поиска (дерево сортировки) для входной последовательности чисел 7 2 5 1 8 3 6 4 9 13 11 10 12, а затем распечатайте вершины этого дерева в порядке обхода в ширину. Какая последовательность чисел получится?

Ответ:

---

Номер 3

Постройте дерево бинарного поиска (дерево сортировки) для входной последовательности чисел 7 2 5 1 8 3 6 4 9 13 11 10 12, а затем распечатайте вершины этого дерева в порядке прямого обхода. Какая последовательность чисел получится?

Ответ:

---

Упражнение 3:

---

Номер 1

В какой последовательности распечатает вершины графа, заданного этим списком смежности, процедура обхода в ширину? (Обход начинается с вершины a, производится в алфавитном порядке.)a: b d
b: d f
f: c d g
d: h g
h: g

Ответ:

---

Номер 2

В какой последовательности распечатает вершины графа, заданного этим списком смежности, процедура прямого обхода? (Обход начинается с вершины a, производится в алфавитном порядке.)a: b d
b: d f
f: c d g
d: h g
h: g

Ответ:

---

Номер 3

В какой последовательности распечатает вершины графа, заданного этим списком смежности, процедура обратного обхода? (Обход начинается с вершины a, производится в алфавитном порядке.)a: b d
b: d f
f: c d g
d: h g
h: g

Ответ:

---

Упражнение 4:

---

Номер 1

Какой алгоритм реализует приведенная ниже программа?const nnn = 10000;
type uk = ^ukk;
     ukk = record v: integer;
                  next: uk;
              end;
var head: array[1..nnn] of uk;
    a: array[1..nnn] of integer;
    ii,i,j,k,n: integer;
    q,p: uk;
    f: text;

procedure dob(ii,jj: integer); {добавление ребра}
var pp,qq: uk;
begin
 new(qq);
 qq^.v:=jj;
 qq^.next:=nil;
 if head[ii]=nil
  then head[ii]:=qq     {вставка первого}
  else begin            {вставка остальных}
        pp:=head[ii];
        while pp^.next<>nil do pp:=pp^.next;
        pp^.next:=qq;
       end;
end;

begin
{------- считывание графа ------------}
 ...
 readln(f,n);	{кол-во вершин в графе}
 while not eof(f) do
  begin
   read(f,i,j);
   if i<>j then begin
                 dob(j,i);
                 dob(i,j);
                end;
  end;
{--------- инициация массива ---------}
 for i:=1 to n do begin
                       head[i]:=nil;
                       a[i]:=0;
                      end;
{------- основная часть -------------}
 k:=0;    
 i:=1;
 repeat
  k:=k+1;
  a[i]:=k;
  p:=head[i];
  while p<>nil do
   begin
    j:=p^.v;
    a[j]:=k;
    if (head[j]<>nil) and (i<>j)
     then begin
           q:=p;
           while q^.next<>nil do q:=q^.next;
           q^.next:=head[j];
           head[j]:=nil;
          end;
    p:=p^.next;
   end;
  i:=i+1;
  while (head[i]=nil) and (i<=n) do i:=i+1;
 until i=n+1;
 
 for i:=1 to n do
  if a[i]=0 then k:=k+1;
 
 writeln(k); {выдача результата}
end.

Ответ:

---

Номер 2

Какой алгоритм реализует приведенная ниже программа?const nnn=10000;
type s1 = ^s2;
     s2 = record n,k,v: integer;
                 next: s1;
          end;
var f: text;
    head,p,q: s1;
    x,i,kr,vr,nxt,kol_ver: integer;
    a: array[1..nnn] of integer;

begin
 assign(f,'in');
 reset(f);
 readln(f,kol_ver);
 new(head);
 with head^ do readln(f,n,k,v);
 head^.next:= nil;
 while not eof(f) do
  begin
   new(q);
   with q^ do readln(f,n,k,v);
   q^.next:= nil;
   if q^.v <= head^.v
    then begin q^.next:= head;
               head:= q;
               continue
         end;
   p:= head;
   while p^.next<>nil do
    begin
     if q^.v > p^.next^.v
      then p:= p^.next
      else begin
            q^.next:= p^.next;
            p^.next:= q;
            break;
           end;

    end;
   if p^.next = nil then p^.next:= q;
  end;
 close(f);

p:=head;
while p<>nil do begin
write(p^.v,' '); p:=p^.next;
end;
writeln('*');

 for i:= 1 to kol_ver do a[i]:= 0;
 kr:= 0;
 vr:= 0;
 nxt:= 0;
 p:= head;
 while (p^.next <> nil)and(kr<kol_ver)do
  with p^ do
   begin
    if a[n]=0
     then if a[k]=0
            then begin inc(kr);
                       inc(vr,v);
                       inc(nxt);
                       a[n]:= nxt;
                       a[k]:= nxt;
                 end
            else begin a[n]:= a[k];
                       inc(vr,v);
                 end
     else if a[k]=0
            then begin a[k]:= a[n];
                       inc(vr,v);
                 end
            else if a[n]<>a[k]
                   then begin x:= a[k];
                              for i:= 1 to kol_ver do
                                if a[i]=x then a[i]:=a[n];
                              inc(vr,v)
                 end;
    p:= next
   end;

 writeln(vr)
end.

Ответ:

---

Номер 3

Какой алгоритм реализует приведенная ниже программа?type vertices = ^vertex;
     edges = ^edge;
     vertex = record id,dist: integer;
                     incidence: edges;
                     next: vertices;
              end;
     edge = record from,toward: vertices;
                   len: integer;
                   next: edges;
            end;
     ptr_edges = ^ptr_edge;
     ptr_edge = record e: edges;
                       next: ptr_edges;
                end;

var i,j,len,source_id: integer;
    g,source: vertices;
    queue,head,next_head: ptr_edges;
    f: text;

function new_vertex(i: integer; g: vertices): vertices;
var v: vertices;
begin
 new(v);
 v^.id:= i;
 v^.dist:= maxint;
 v^.incidence:= nil;
 v^.next:= g;
 new_vertex:= v
end;

function find_vertex(i: integer; g: vertices): vertices;
var v: vertices;
begin
 v:= g;
 while (v<>nil)and(v^.id<>i) do v:= v^.next;
 find_vertex:= v
end;

function find_edge(j: integer; n: edges): edges;
var e: edges;
begin
 e:= n;
 while (e<>nil)and(e^.toward^.id<>j) do e:= e^.next;
 find_edge:= e
end;

procedure new_edge(i,j,len: integer; var g: vertices);
var vi,vj: vertices;
    eij: edges;
begin
 vi:= find_vertex(i,g);
 if vi = nil 
   then begin g:= new_vertex(i,g);
              vi:= g
        end;
 vj:= find_vertex(j,g);
 if vj = nil 
   then begin g:= new_vertex(j,g);
              vj:= g
        end;
 eij:= find_edge(j,vi^.incidence);
 if eij = nil
   then begin new(eij);
              eij^.from:= vi;
              eij^.toward:= vj;
              eij^.len:= len;
              eij^.next:= vi^.incidence;
              vi^.incidence:= eij
        end
end;

procedure enqueue(v: vertices; var q,h: ptr_edges);
var e: edges;
    pe: ptr_edges;
begin
 e:= v^.incidence;
 while e<>nil do
  begin
   new(pe);
   pe^.e:= e;
   pe^.next:= nil;
   if q = nil
     then h:= pe
     else q^.next:= pe;
   q:= pe;
   e:= e^.next
  end
end;

procedure print_vertices(g: vertices);
var v: vertices;
begin
 v:= g;
 while v<>nil do 
  begin
    writeln(source_id,' -> ',v^.id,' : ',v^.dist);
    v:= v^.next
  end
end;

procedure dispose_edges(n: edges);
var e,e_next: edges;
begin
 e:= n;
 while e<>nil do 
  begin
    e_next:= e^.next;
    dispose(e);
    e:= e_next
  end
end;

procedure dispose_vertices(g: vertices);
var v,v_next: vertices;
begin
 v:= g;
 while v<>nil do
  begin
    v_next:= v^.next;
    dispose_edges(v^.incidence);
    dispose(v);
    v:= v_next;
  end;
end;

begin
 assign(f,'in');
 reset(f);
 readln(f,source_id); {в первой строке записана начальная вершина}
 g:= nil;
 while not eof(f) do
  begin
   readln(f,i,j,len); {граф задан списком ребер: от, до, длина}
   new_edge(i,j,len,g);
   new_edge(j,i,len,g);
  end;
 source:= find_vertex(source_id,g);
 source^.dist:= 0;

 queue:= nil;
 head:= nil;
 enqueue(source,queue,head);
 while head<>nil do 
  begin
   with head^.e^ do
     if from^.dist+len < toward^.dist 
       then begin
              toward^.dist:= from^.dist + len;
              enqueue(toward,queue,head);
            end;
   next_head:= head ^.next;
   dispose(head);
   head:= next_head
  end;
 print_vertices(g);
 dispose_vertices(g);
end.

Ответ:

---