中科院计算机技术研究所1995年硕士生入学试题程序设计

一.选择
1.一棵深度为6的平衡二叉树,其每个非终端结点的平衡因子均为1,则该树共有__个终端结点.(2分)
a.14
b.16
c.18
d.20
e.22
f.24

2.一个有18条边的非连通无向图,至少应有__个结点.(2分)
a.6
b.7
c.8
d.9
e.10
f.11

3.一棵124个叶结点的完全二叉树,最多有__个结点.
a.247
b.248
c.249
d.250
e.251(2分)

4.按锦标赛排序的方法，决定出8位运动员之间的名次顺序排列,至少需编排__场次的比赛.(考虑最坏)
a.13
b.14
c.15
d.16
e.17
(2分)

5.已知Head(Tail([Head(S),Head(Tail(Tail(S))]))广义表满足上式,则S为___.
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]]
(其中,方括号表示广义表,圆括号表示函数,Head()表示取广义表的头部)(2分)

6.在下列三种次序的线索二叉树中,___对查找指定结点在该次序下的后继效果较差.(2分)
a.前序线索树b.中序线索树c.后序线索树

7.由二叉树的前序和后序遍历序列___唯一地确定这棵二叉树.(2分)
a.能b.不能

8.在下列两种求图的最小生成树的算法中,__算法最适合于求边稀疏的网的最小生成树(2分)
a.Primb.Kruskal

9.下列无向图的存储结构中,在对无向图的边进行操作时,(如删除一条边)___存储结构更为适合.
a.邻接表
b.邻接多重表.

10.在下述几种树当中,__可以表示静态查找表.
a.次优查找树;
b.二叉排序树;
c.B-树
d.平衡二叉树

11
(1).在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_A__.
(2).快速排序在最坏的情况下,时间复杂度是_B__,_C__的性能差;
(3)就平均时间而言,_D__最佳.
A.:(1)直接插入排序(2)起泡排序(3)简单选择排序;
B.:(1)O(nlog(n))(2)O(n^2)3.O(n^3)
C.:(1)堆排序(2)起泡排序(3)选择排序.
D.:(1)堆排序(2)快速排序(3)归并排序.

12.一程序规定的职能是"输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形.再做计算..."若用等价类划分方法对该程序作功能测试,至少应对该程序的输入数据考虑_A_个等价类,其中包括_B_个有效等价类和_C_个无效等价类.
A.___B.___C.___
(1)3;(2)5;(3)7;(4)12;(5)15;(6)18;(7)21;(8)25;(9)33;(10)40;

13.设二叉树如图所示:

1.给出先序遍历的结点,访问顺序________.
2.给出中序遍历的结点,访问顺序________.
3.给出后序遍历的结点,访问顺序________.
4.若用二叉链表作为存储结构,将出现多少个空指针域?__
(共四分)

14.下列函数
functioncalc(x,y:integer):integer;
begin
ify=1thencalc:=x
elsecalc:=calc(x,y-1) x
end;
a,b均为正整数,则calc(a,b)=___.
(1).a*(b-1)
(2).a*b
(3)a b
(4)a a

15.程序段
read(a,b);
c:=3.0*a b;
ifc=0thena:=1
elsea:=1.0 1.0/c 1.0/b;
保证该程序段运行不出错的必要条件是:___
(1).b>0;
(2).a>0andb>0;
(3).b!=0;
(4).b!=0andc!=0;

二.程序改错与填空:
1.指出下列程序段中的错误位置,对错误编号说明理由:
程序段1:(8分)
Label1:
constmax=50;
typeday={Mon,Tue,Wed,Thu,Fri,Sat,Sun};
vardate:day;
N:integer;
begin
a:N:=N-ord('0');
b:fordate:=MontoSundo
N:=ord(succ(date))-1
c:forn:=1to10do
begin
......
1:语句;
end;
......
goto1;
......
end.
答:__________________________.

程序段二.(8分)
Programtype(input,output);
varR:real;
Procedureprint(varx:integer,y:real);
varz:real;
Proceduresum(x:integer;y:real);
vark:real;
begin
z:=x y;
k:=3*z;
x:=x y;
end;{sum}
begin
sum(x,y);
writeln(x,y,z,k);
end;{print}
begin
readln(R);
print(15,R);
print(R,R)
end.{mainprogam}

2.阅读下列程序,填空使之成为一个完整的程序:
该程序输出N个元素的全排列.
程序:
programpic(input,output);
constn=10;
varA:array[1..n]ofinteger;
i,k:integer;
procedureoutput1;
begin
fori:=1tondo
write(A[i]:3);
writeln;