2000厦大计算机考研真题

厦门大学 2000

一 阅读程序，写出输出结果。 1 program ge01;

type intfunc = function (x:integer): integer; var a,b:integer ;

procedure fcm(f: intfunc ; m:integer; var k:integer); var t:integer;

begin t:=m+k ; k:= f(t) div 5 end; function cy (x:integer) :integer; begin cy:=x mod 7 end; begin

a:=11; b:=16 ; fcm (cy,a,b); writeln (a:6,b:6) end.

2 program ge02;

var a,b,c: integer;

function fc (n: integer): integer; function fd(n:integer) :integer; procedure ps(var k: integer); begin k:=a+2; c:=3*k end;

begin ps(b); n:=a+4; fd:=n*b end; begin m:=m+2j; fc:=fd(b)-m end; begin

a:=1; b:=3;c:=2;

writeln('fc=', fc(a):6); writeln ('a=', a:4, ' b=', b:4, ' c=',c:4);

end.

二 1 type

ctype=array[0..100] of real;

function p(var a:ctype ; n:integer; x:real) : real; begin

if n=0 then p:=a[0]

else p:=p(a, n-1,x)*x +a[n] end; 2 type

vtype=array [1..100] of integer;

function m(var a:vtype; n :integer):real; begin

if n=1 then m:=a[1] else if m(a,n-1)>a[n]

then m:=m(a,n-1)

else m:=a[n] end. 三 1 type

tree=^node ; node= record

data :integer ; left ,right:tree end;

procedure preorder(t:tree ); var

stack: array [1..100] of tree;

说明下列函数分别实现什么功能。 填空

以给如下关于二叉树的类型说明： 以下过程实现对二叉树前序遍历的非递归算法：

nd: tree; top : integer; begin

top :=1 ; stack[top ]:=t;

while --------------- do begin

nd :=stack[top ]; top:=top -1;

write (nd^.data);

if (nd^.right<> nil) then begin

top :=top +1; -------------------- end;

if ---------------- then begin

-----------------------

stack [top ]:= nd^.left end end end;

2 以给如下关于单链表的类型说明： type

list=^node ; node=record

data: integer; next: list; end;

以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.

procedure mergelink(var p,q:list): var h,r:list; begin

-----------

h^.next:= nil ; r:=h;

while ((p<>nil) and (q<>nil)) do i f p^.data<=q^.data) then begin

-----------------

r:=p ; p :=p^.next; end else

begin

----------------- r:=q; q:=q^.next; end;

if (p=nil ) then r^.next :=q; --------------------------

p:=h^.next ; dispose(h); end;

四 编程

1 编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都为空或都只有一个结点，要么它们的左右子树都相似。

2 广义表gl=(a1 ,a2 .....an),其中 ak(k=1,2,...n)或是单个数据元素（原子），或仍然是个广义表。给定如下有关广义表的类型定义：

type

tagtype =0..1; glist=^gnode; gnode=record link:glist;

case tag:tagtype of 0: (data :integer); 1:(sublist: glist) end;

编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表（3， （2，4，5），（6，3）） 数据域之和为23。

五 问答题：

1 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别； 头结点与首元结点的关系。

2 指出树和二叉树的主要区别。

3 数组a[0..8, 1..10] 的元素是6 个字符组成的串，则存放a至少需要多少个字节？ a 的第8列和第5行共占多少个字节 ？ 若a 按行优先方式存储，元素a[8,5]的起始地址与当a按列优先方式存储时的哪个元素的起始地址一致？

六 填空

1 循环队列用数组a[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是--------------------------。

2 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有-------------个叶子结点。

3 设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中关键码按字母升序重新排序， （！） 是初始步长为4的shell排序一趟扫描的结果； （ ）

（2） 是对排序初始建堆的结果； （ ） （3） 是以第一个元素为分界元素的快速一趟扫描的结果。 （ ） 从下面供选择的答案中选出正确答案填入括号内。

A f ,h ,c ,d ,p ,a ,m ,q , r ,s ,y , x B p, a, c, s, q, d, f, x, r, h, m, y C a, d, c, r, f, q, m, s, y, p, h, x D h, c, q, p, a, m, s, r, d, f, x, y E h, q, c, y, a, p, m, s, d, r, f, x 七 作图

1 已知某二叉树的后序遍历和中序遍历如下，构造出该二叉树。 后序遍历序列： G D B E I H F C A 中序遍历序列 ： D G B A E C H I F 2 已知如下所示长度为12的表（jan , feb, mar apr , may, june , july, aug, sep , oct, nov, dec)按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度asl.

3 下图是5阶B树 ，画出删去P后的B树，再画出删去D后的B树。