厦门大学2000年数据结构和高级程序设计考研试题

1、厦门大学2000年数据结构和咼级程序设计考研试题測直h打出输出结果.programgeO1；lypuintTunc=fundion（K：iniegcr）:iniegcr;varnTb:inter;procedurefcm(f:intfunc;mzinteger;vark:integer);vart:inleger;begint:=m+k;k:=f(t)div5end;functioncy(x:inlcgcr):irHeger;begincy:=xmod7end;begina:=11;b:=16;fem(cy,a,b);writcln(a:6,b:6)end9programgc02;vara,b

2、,c:integer;functionfc(n:integer):integer;functionfd(n:intcgcr):inieger;procedureps(vark:integer);begink:=a+2;c:=3Mkend;beginps(b);n:=a+4;fd:=nHbend;beginm:=m+2j;fc:=fd(b)mend;begina:=1;b:=3;c:=2;writcln(*fc=fc(a):6);writcln(*a=a:4t1b=b:4,*c=c:4);end二说明K列闻数分别实现什么功能。1typectypc=array0.100ofreal;functio

3、np(vara:ctypc;n:intcgcr;x:real):real;beginifn=0thenp:=a0elsep:=p(a,n-1,x)Mx+anend;typevtypc=array1.100ofinteger;vtypc=array1.100ofinteger;functionm(varbeginifn=1elsea:vtypc;n:integer):real;thenm:=a|1ifm(a,n-1)>a|n|thenm:=m(a,n-1)elsem:=an三 填空1以给如下关于二义树的类型说明：typetrcc=Anodc;nodc=recorddata:integer;

4、left,right:trccend;以卜过桎实现对二义树前序遍历的非递归算法:procedureprcordcr(t:tree);stack:arrayI.100oftree;nd:tree;top:integer;begintop:=1;stacktop:=t;whiledobeginnd:=stacktop|;top:=top-1;write(ndA.data);(ndA.FighioniI)thenbcgin:=top+1;:=top+1;end;ifthenbeginstacktop:=ndA.lcflendendend;2以给如下关于单链表的类型说明：typelist=Anodc;

5、nodc=rccorddata:integer;next:list;end;以卜用序采用链表合并的方法，将两个已拮序的单链表合并成一个链表而不改变其排序性(升序)，这里两链表的头指针分别为P和ceduremcrgclink(varp,q:list):varh9r:list;beginhncxt:«=nil;r:=h;while(p<>ni1)and(qonil)doifpA.data<=qAdnla)thenbeginr：=Pr：=Pp:=pAnext;endr:=q;q:=qA.next;end;thenthen"nextp:=hA.next;

6、disposc(h);end;编程I编写一个幣数或过程判定两棵二义树是否相似，所谓两棵二义树S和I相似，即是耍么它们都为空或都只仃一个结点，耍么它们的左右子树都相似。2广义表gl=(al,a2an),其中ak(k=l,2,.n)或是单个数据元索(原子)，或仍然是个广义表.给定如卜仃关广义表的类型定义：typetagtypc=U.1;glist=Agnodc;gnodc=rccordlink:glist;easetag:tagtypcof0:(data:integer);1:(sublist:glist)end;编写一个过程或嗨数计算一个广义表的所右原子结点数据域Z和.例如对广义表(3.(2.4

7、>5).(6.3)数据域Z和为23。四 问答题:1 说明在线性农的链式存储结构中，头指针与头结点Z间的根木区别：头结点与首元结点的关系。2指出树和二叉树的主要区别。3数组a0.8,I.10的元索是6个字符组成的串，则存放n至少需耍多少个字节？a的第8列和第5行共占多少个字节？若“按行优先方式存储，元素“【8,5|的起始地址与半。按列优先方式存储时的哪个元素的起始地址一致？五 境空1循环队列用数组aO.m-l|存放其元索值，已知其头尾指针分别是from和rear,则当前队列的元索个数是2 已知一棵度为3的树右2个度为I的结点，3个度为2的结点，4个度为3的结点，则该树冇个叶子结点。3设要将

8、序列（q'h'C'y'P'Sm'SbcLf'X）中关键码按字母升序重新挥序，（!）是初始步长为4的shell排序一越打描的结果：（）（2）是对排序初始建堆的结果：（）（3）是以第一个元索为分界元秦的快速一越扫描的结果.（）从卜面供选样的答案中选出正确答案填入括号内。Bp$a9c.s9q,d,f,rt9y.p,h,xDh.c,q.p,a,m,s,r,d.f,x,yEh,q,c,y,a,p.m,s.d9r,f9x六 作图1已知某二叉树的后序遍历和屮序遍历如卜，构造出该二叉树。后序遍历序列：GDBEIHFCADGBAECHIF中序遍历序列:2 (2知如卜所示长度为12的表(jun,