厦门大学2002年硕士研究生入学考试数据结构和高级程序设计

厦门大学2002年硕士研究生入学考试数据结构和高级程序设计 一、１６分 1、PROGRAM g0101 ( output ); var a,b :integer ; FUNCTION fc( x : integer ) : integer ; begin a:=b+x ; x=b-x ; fc:=a*x ; end ; FUNCTION fp ( VAR y :integer ) : integer ; begin y:=b+y ;

厦门大学2002年硕士研究生入学考试数据结构和高级程序设计

一、１６分
1、PROGRAM g0101 ( output );
  var a,b :integer ;
  FUNCTION fc( x : integer ) : integer ;
   begin a:=b+x ; x=b-x ; fc:=a*x ; end ;
  FUNCTION fp ( VAR y :integer ) : integer ;
   begin y:=b+y ;fp=y-a ; end ;
  begin
    a=2; b=3;
    writeln(＇fc=＇ , fc(a) , ＇ fp= ＇ ,fp(b) ) ;
    writeln( ＇a=＇ ,a , ＇b=＇ b )
  end;

2、PROGRAM g0102 (output );
  var a,b,c:integer ;
  begin
    new(a); a^:=3; new(b); b^5:=5 ;
    a^:=a^+b^ ; c:=a;
    c^:=a^*b^; b^:=a^-c^ ;
    writeln( ＇a=＇,a^,＇b=b＇,b^,＇c=＇,c^ );
  end;
3、PROGRAM g0103 (output) ;
  const a=3 ; b=4 ;c=7 ;
  var
    x:=array[1..a] of integer ;
    y:=array[1..b] of integer ;
    z:=array[1..c] of integer ;
    i,j,k,h:integer ;
  PROCEDURE ssar ;
    var i,j,k:integer ; w:array[1..a]of integer ;
  begin
    for i:=1 to a do w[i]:=x[a+1-i];
    i:=1 ;j:=1;k:=1;
    while (i<=a) and (j<=b) do
     begin
       if  w[i] > y[i] then begin h:=w[i] ; i=i+1; end
       else begin h:=y[i] ; j:=j+1 ;end;
       z[k]:=h ; k:=k+1 ;
     end ;
    while i<=a do begin z[k]:=w[i] ;k:=k+1; i:=i+1 end;
    while j<=b do begin z[k]:=y[i] ;k:=k+1; j:=j+1 end;
  end;
  begin
     for i:=1 to a do x[i]:=i*2 ;
     for j:=1 to b do y[i]:=c-j ;
     ssar ;
     for i:=1 to c do write(z[i],＇＇); writeln;
  end ;

4 PROGRAM g0104 (output);
  var a,b,c:integer;
  FUNCTION fg(x:integer ;var y,z:integer):integer ;
    begin z:=x*2; x:=z+1 ; y:=x+z ; fg :=y-1 ; end
  begin
    a:=1 ;b:=2;c:=1;
    writeln(＇fg=＇,fg(fg(a,b,c),b,c)) ;
    writeln(＇a=＇,a,＇b=＇,b,＇c=＇,c) ;
  end;

二、１２分已知双连表中节点类型如下

  Type
   dpoint = ^list ;
   list =RECORD  
    data:integer;
    left ,right : dpointer ;
   end ;

如下过程将在双连表第i个节点（i>=0）之后插入一个元素，为x的结点，请在答案栏给出题目中______处应该添入的语句或表达式，使之完成上述功能。

PROCEDURE insert ( var head :dpointer ;i,x:integer);
  var s,p:dpointer ;
    j:integer;
  begin
    new(s) ;s^data:=x;
    if (i=0) then { 如果i=0，则将s结点插入到表头后返回}
      begin s^.right=head ;____1_____ head:=s ; end
    else
      begin
       p:=head; ____2____ {在双连表中查找第i 个节点，由p所指向}
       while ((p<>nil) and (j<i) do
         begin j:=j+1 ; _____3______ end ;
       if(p<>nil) then
         if (p^.right=nil) then
           begin p^.right:=s ; s^.right:=nil ; ____4___ end;
         else
           begin s^.right:=p^.right ; ___5____
              p^.right:=s; ____6_____ end
       else
       writeln(＇can not find node ＇);
      end;
  end;

三、１２分广义表是n(n>=0)个数据元素，a1,a2,……an的有限序列，
其中ai（1<=i<=n）或者是单个数据元素（原子），或仍然是一个广义表，广义表的结点具有不同的结构，即原子结点和子表结点，为了将两者统一，link域指向下一个结点，当其tag为１时表示是子结点，其sublist为指向子表的指针。因此，广义表可采用如下结构存储：
type
  glist=^gnode ;
  gonde=RECORD
  link:glist;
  case tag:0..1 of
   0data:char);
   1sublist:glist);
end;

１、画出广义表（（a,b),c）的存储结构；
２、写出计算一个广义表的原子结构个数的递归算法表示式；
３、编写实现上述算法的过程或函数程序。

四、１０分写一个算法，利用［０。。１］上的随即函数计算圆周率n的近似值，首先说明你的算法，而后编写相应的过程或函数程序。

五、选择踢　（８分）
１、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据特性的影响的是________.

a 直接插入排序　　b　快速排序　　c　直接选择排序　　　d　堆排序

２、下列排序算法中，占用辅助空间最多是_______

a　归并排序　　　b　快速排序　　c　希尔排序　　d　堆排序

六、填空２０分

１、一棵左子树为空的二叉数在先序线索化后，其中的空链域的个数为______

2、若以｛４、５、６、７、８｝做为叶子节点的权值构造哈夫曼树，则其带权路径长度是________
3、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是_______

剩下的省略…………
填空还有２题，都是基本题，七是作图题１２分，给你一些中序、先序、后序的字母，让你画出，完整的二叉树。（给你的三个序列都是不完整的）

八是解答题１０分，一道是给你一个图，要你找到，顶点１到其余各点的最短路径
还有一个二叉树的题目。