一、下面关于程序设计风格的叙述，那些是正确的？那些是错误的？（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分）
