中科院计算机技术研究所1994年程序设计试题
中科院计算机技术研究所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、次子程序的功能是什么?
……
type m=array[0..n] of integer;
procedure count (b:m);
var i,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等均是回文。
程序：
program palindrome(input,output);
const max=1000;
var n,m,i,j,s:integer;
d: array [1..max] of integer;
begin
read(n);
for m:=1 to n do
begin
______A________
j:=0;
while ____B______ do
begin
j:=j+1;
d[j]:= s mod 10;
______C_________
end;
i:=1;
while (d[i]=d[j] and ______D______ do
begin
i:=i+1; j:=j-1;
end;
if ____E____ then write (m)
end
end.
答案：[A]________________ [B]__________________
[C]________________ [D]__________________
[E]________________
七、编写一个子程序，对于给定的正整数N和M(N〈M)，打印出所有满足条件I1+I2+…+IN = M的正整数序列
I1，I2，…IN，其中I1〉I2〉…IN。例如N=4，M=8时，打印结果如下： (10分)
5 1 1 1
4 2 1 1
3 3 1 1
3 2 2 1
2 2 2 2
八、设二叉树用二叉链表表示，试写一算法输出其嵌套括号表示。例如下面图示的二叉树，其输出形式为A(B(，D)，C) (15分)