Какой алгоритм реализует приведенная ниже программа?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.

Правильный ответ:

• # На сколько компонент связности распадается граф, содержащий семь вершин, если он задан таким списком ребер?a g a d b c c h f b f c
• # В дереве 10 ребер. Сколько в нем вершин?
• # Процесс поиска и исправления синтаксических и логических ошибок в программе называется
• # Какая последовательность символов будет содержаться в файле f: file of char после выполнения следующего отрывка программы: rewrite(f); for c:= '0' to '9' do write(f,c); {c: char} seek(f,5); read(f,c); write(f,c); seek(f,3); truncate(f); seek(f,9); write(f,c);
• # Имеется набор натуральных чисел, быть может, с повторениями. Необходимо разделить его на два поднабора так, чтобы разность сумм весов была минимальной. Эта задача решается рекурсивным методом полного перебора с отсечением (см. ниже). На вход были поданы числа 18 32 5 5 6 2 78 4 56 5 2. При какой глубине стека контекстов произойдет завершение работы программы (обращение к завершающей процедуре out())? {массив а хранит веса всех предметов, в порядке их ввода, half - "большая" половина суммы всех весов, dif - отклонение текущей найденной суммы от half} procedure rec(k: byte; sum: longint; var dif: longint); var i: byte; begin if sum+a[k]<=half then for i:= k+1 to n do rec(i,sum+a[k],dif) else if half-sum<dif then begin dif:= half-sum; if dif<2 then out(dif){печать и завершение} end end;