中国科学技术大学1996年硕士入学考试程序设计试题
　　一、单项选择：(20分)
　　1、具有N个结点的完全二叉树的深度是：( )
　　(1)[log2n] (2)[LOG2N]/1 (3)[LOG2(N/1)] (4)[LOG2N]-1
　　2、用单循环链表表示队列，正确的说法是：( )
　　(1)可设一个头指针使入队、出队都方便
　　(2)可设一个尾指针使入队、出队都方便
　　(3)必须设头尾指针才能使入队、出队都方便
　　(4)无论如何,只可能使入队方便
　　3、对无向图而言，同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一个结点表示，故此邻接多重表所需存储量比邻接表( )
　　(1)少一半 (2)多，但差异不大 (3)少，但差异不大
　　4、一个哈希函数被认为是“好的”，如果它满足条件()
　　(1)哈希地址分布均匀
　　(2)保证不产生冲突
　　(3)所有哈希地址在表长范围内
　　(4)满足(2)和(3)
　　5、ISAM文件和VSAM文件属于( )
　　(1)索引非排序文件
　　(2)索引顺序文件
　　(3)顺序文件
　　(4)散列文件
　　6、在下述排序算法中( )算法是稳定的排序算法。
　　(1)希尔排序
　　(2)快速排序
　　(3)冒泡排序(BUBBLE SORT)
　　7、平衡二叉树中，若某个结点在左、右子结点的平衡因子为零，则该因子的平衡因子也一定是零，这种说法( )
　　(1)不正确 (2)正确
　　8、在下述三种排序算法中，所需辅助存储量最多的是( )，所需存储量最少的是( )，平均速度最快的是( )
　　(1)堆排列 (2)快速排列 (3)归并排列
　　二、问答题(25分)
　　1、已知某电文中共出现十种不同的字母，各个字母出现的频率分别为A：8，B：5，C：3，D：2，E：7，F：23，G：9，H：15，I：3，J：35，现在对这段电文用三进制进行编码(即码字由0，1，2，组成)，问电文编码总长度最少有多少位?并画出图。
　　2、A是一个三对角短阵、行数与列数相等，用压缩存储的方法将其压缩存储列一堆的数组SA[1 3n-2]中(按行顺序存储)，则SA[K]对应的短阵元素的下标为：行值I=( )，列值J=( )，反过来，若知道A中元素的下标I，J，则其存储住值置K=( )。(写出表达式)
　　3、设A是一个栈，栈中共有N个元素，依次为A1，A2，AN，站顶元素为AN，B是一个循环队列，队列中N个元素依次为B1，B2，BN，对头元素为B1，A，B均采用顺序存储结构且存储空间足够大，现要将站中元素全部移到队列中，使得队列中元素与站中元素交替排列，即B中元素为B1，A1，B2，A2，B3，A3，BN，AN，问至少需要多少次基本操作才能完成上述工作，请写出具体步骤(要求除A，B外所用的其他附加存储量为1，每次出栈、入栈、出队列可均看作一次基本操
　　作)。
　　4、试为下列二叉树建立后序线索，画出相应的后序线索二叉树。
　　三、算法描述(15分)
　　以二叉链表作存储结构，编写按层次顺序(从根结点开始)遍历二叉树的算法。
　　四、阅读下列程序，并回答：下列程序是否正确?为什么?如何修改?
　　var a,b,c,d,e,f :integer;
　　procedure mult(var x,y,z:integer);
　　begin
　　z:=0;
　　while x<>0 do
　　begin
　　if odd(x) then z:=z+y;
　　y:=y+z;
　　z:=x div 2;
　　end;
　　end;
　　begin
　　a:=5;b:=7;d:=11;e:=13;
　　mult(a,b,c);{要求输出c=15}
　　mult(d-b,e-a,f);{要求输出f=32}
　　end.
　　五、阅读下列程序说明和C程序，把应填入其中方框处的字句，写在答卷的对应栏内。
　　[程序说明]
　　对于正整数N，输出其和等于N且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如N=4，程序输出为：
　　4=4
　　4=3+1
　　4=2+2
　　4=2+1+1
　　4=1+1+1+1
　　程序中分别采用递归和非递归解法的两个函数RD

责任编辑:claire