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


一、下面关于程序设计风格的叙述，那些是正确的？那些是错误的？（10分）
1、编写程序是，应使用括号以改善表达式的清晰度。
2、应当尽可能对程序代码进行优化。
3、在程序设计中，不要进行浮点数相等的比较。
4、应尽可能多的输出中间结果。
5、不要使用数据类型来对数据值进行防范。
6、要用计数方法而不是用文件结束符来控制输入的结束。
7、使用有意义的标识符。
8、结构化程序设计语言中没有GOTO语句。
9、一般而言，语言的级别越高，用它编出的程序越短。
10、PASCAL是一种自由格式的弱类型语言。

二、填空：（10分）
1、FORTRAN程序中，变量的作用域以______为单位，PASCAL程序的作用域遵守_____规则。
2、赋值语句A：=A 1左边的A代表_________含义，右边的A代表_________含义。
3、高级程序设计语言的语句分为_________和____________二种。
4、在查找算法中，顺序查找的平均查找长度ASL为________；折半查找的ASL为___________；
而二叉排存树查找记录时，最坏下的情况ASL为__________；在二叉平衡排存树上插入一个结点后,最坏情况需要_______次旋转才能保持平衡。

三、选择填空：（10分）
1、存贮稀疏图的数据结构常有的是。
[1]邻接矩阵[2]三元组[3]邻接表[4]十字链表
2、内部排序多个关键字的文件，最坏情况下最快的排列方法是_____,相应的时间复杂度为______,该算法是的稳定性__________.
[1]快速排序[2]插入排序[3]归并排序[4]简单选择排序[5]O(nlog2(n))[6]O(n^2)[7]O(n^2log2(n))[8]O(n)[9]稳定[10]不稳定
3、倒排文件包含若干个倒排表，倒排表的内容是_____________.
[1]一个关键字值和关键字的记录地址；
[2]一个属性值和该属性的一个记录地址；
[3]一个属性值和该属性的全部属性地址；
[4]多个关键字值和它们对应的某个记录的地址。
4、设T为哈夫曼最优树，具有5个叶结点，树T的高度最高可以是__________.
[1]1，[2]2，[3]3，[4]4，[5]5，[6]6
5、对正确的AOE网络图而言，必须是____,AOE中某边权值应当是_____,权值为0的边则表示______.
[A]，[1]完全图；[2]哈密顿图；[3]无环图；[4]强连通图
[B]，[1]实数；[2]正整数；[3]正数；[4]非负数
[C]，[1]为决策而增加的活动；[2]为计算方便而增加的活动；[3]表示活动间的时间顺序关系；[4]该活动为关键活动。
6、假定有K个关键字互为同义词，若用线性探测法把这K个关键字插入表中，至少需要____次探测。
[1]K-1[2]K[3]K 1[4]K（K 1）/2

四、（10分）设图G有N个顶点，G的邻接矩阵A定义为：
A[I，J]=1//如果存在I到J的边
0//否则
G的传递闭色矩阵A 定义为
A [I，J]=1//如果存在I到J的路径
0//否则
（1〈I，J〈N）
本算法框图的功能是求A的传递闭色A ，试填充[1]~[5]使之成为完整的算法。
图中PATH和A均为N*N的布尔矩阵。
答案：[1]__________________[2]________________[3]__________________[4]________________[5]__________________


五、阅读如下子程序，回答下列问题：（10分）
1、当数组B的值为（1，1，1，1，2，2，3，3，3，3，3，4，4，）时，此子程序的输出结果是什么？
2、次子程序的功能是什么？
……
typem=array[0..n]ofinteger;
procedurecount(b:m);
vari,l:integer;
begin
i:=1;l:=1;
while(i<=n)do
begin
if(b[i]=b[i-l])then
l:=l 1;
i:=i 1;
end
write(l)
end;

六、阅读如下程序，并填充[A]~[E]，使之成为一个完整的程序。（10分）
本程序输入一个给定的正整数N，打印出所有不超过N的，其平方为回文的数。
回文是指字符串两半的字符左右对称，例如1，22，121，4224等均是回文。
程序：
programpalindrome(input,output);
constmax=1000;
varn,m,i,j,s:integer;
d:array[1..max]ofinteger;
begin
read(n);
form:=1tondo
begin

______A________
j:=0;
while____B______do
begin
j:=j 1;