资源描述：
《中国科学技术大学考研试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、中国科学技术大学一九九五年招收硕士学位研究生入学考试试题试题名称:程序设计一、选择题1.一颗深度为6的平衡二叉树,其每个非终端节点的平衡因子均为1,则该树共有_____个节点.(2分)a)14;b)16;c)18;d)20;e)22;f)242.一个有28条边的非连通无向图,至少应有____个节点.(2分)a)6;b)7;c)8;d)9;e)10;f)113.一颗124个叶节点的完全二叉树,最多有___个节点.(2分)a)247;b)248;c)249;d)250;e)2514.按锦标赛排序的方法,决定出8位运动员之间的名次顺序排列,至少需编排____场次的比赛.(考虑最坏情况
2、)(2分)a)13;b)14;c)15;d)16;e)175.已知Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a],广义表S满足上式,则S为______.(其中,方括号表示广义表,圆括号表示函数,如[a,b]表示由a,b构成的广义表,而Head()表示取广义表的头部.)(2分)a)[[a,b],b,a]b)[[b,a],[a],[b]]c)[[a],[a,b],[b]]d)[b,[a],[a,b]]e)[[a],[b],[b,a]]f)[[b],[b,a],[a]]6.在下列三种次序的线索二叉树中,___对查找指定节点在该次序下的后继效
3、果较差.(2分)a)前序线索树b)中序线索树c)后序线索树7.有二叉树的前序和后序遍历序列唯一的确定这颗二叉树.(2分)a)能b)不能8.在下列两种求图的最小生成树的算法中,___算法适合于求边稀疏的网的最小生成树.(2分)a)Prim;b)Kruskal9.下列无向图的存储结构中,在对无向图的边进行操作时(如删除一条边)____存储结构更为合适a)邻接表b)邻接多重表10.在下述几中树中,___可以表示静态查找表.(2分)a)次优查找树;b)二叉排序树;c)B-树d)平衡二叉树11.答案写在填空的字母后面(1)在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是A(
4、2)快速排序在最坏情况下,时间复杂度是B,比C的性能差(3)就平均时间而言,D最佳(共4分)A:a)直接插入排序;b)起泡排序;c)简单选择排序;23B:a)O(nlogn);b)O(n);c)O(n)C:a)堆排序;b)起泡排序;c)选择排序D:a)堆排序;b)快速排序;c)归并排序12.一程序规定的职能是:“输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形,再做计算…….”.若用等价类划分方法对该程序做功能测试,至少应对该程序的输入数据考虑A个等价类,其中包括B个有效等价和C个无效等价类.A,B,C:(答案写在填空的字母后面)(1)3;(2
5、)5;(3)7;(4)12;(5)15;(6)18;(7)21;(8)25(9)33;(10)4013.二叉树如图所示（1）给出先序遍历的节点的顺序;_________（2）给出中序遍历的节点的顺序;_________（3）给出后序遍历的节点的顺序;_________（4）用二叉链表作为存储结构,将出现多少个空指针(nil)域?_____(共4分)14.下列函数(6分)functioncalc(x,y:integer):integer;beginify=1thencalc:=xelsecalc:=calc(x,y-1)+xend;a,b均为正整数,则calc(a,b)=____
6、__1)a*(b-1);2)a*b;3)a+b4)a+a15.程序段read(a,b);c:=3.0*a+b;ifc=0thena:=1elsea:=1.0+1.0/c+1.0/b保证该程序段运行不出错的必要条件是:_______.(4分)（1)b>0（2)a>0andb>0（3)b¹0（4)b¹0andc¹0二、程序改错与填空1.指出下列程序段中的错误位置,对错误编号,说明理由:程序段一:(8分)label1;constmax=50;typeday={Mon,Tue,Wed,Thu,Fri,Sat,Sun};vardate:day;N:integer;begina:N:=N-
7、ord('0');b:fordate:=MontoSundoN:=ord(succ(date))–1;c:forn:=1to10dobegin……1:语句;end;……goto1;……end.答:____________________________________________________________________________程序段二.(8分)programtype(input,output);varR:real;procedureprint(varx:integer,y
