中国科学技术大学 一九九七年招收硕士研究生入学考试试题 试题名称：程序设计 选择填空（每空1分，共10分） 查找几个元素的有序表时，最有效的查找方法是______. a: 数序查找; b:分块查找; c:二分查找; d:二叉排序树 对一般二叉树而言,求节点按某种序列的前趋节点变得容易的线索二叉树是___和____. a: 前序线索二叉树; b: 中序线索二叉树; c: 后序线索二叉树 若一个有向图具有拓扑排序序列,那么它的邻接矩阵必定为____. a: 对称矩阵; b: 稀疏矩阵; c: 三角矩阵; d: 一般矩阵 采用开址定址法解决冲突的哈希查找中,发生集聚的原因主要是____. a: 数据元素过多; b: 负载因子过大; c: 哈希函数选择不当; d: 解决冲突的算法选择不好. 对n个关键字的文件进行内部排序,在最好情况下,最快的排序方法是____;相应的时间复杂度为_____;该算法的稳定性是_______. A: ①快速排序; ②插入排序; ③归并排序; ④选择排序 B: ① O(); ② O(n); ③ O(n n); ④ O(n㏑n) C: ①稳定; ②不稳定 在K路平衡归并的外部排序中,如果内部选择算法采用堆排序,则总的排序时间与K______. a: 有关; b: 无关 哈夫曼编码树是一种_____. a: 最优查找树; b: 最优二叉树; c: 平衡二叉树 d: B+树 填空(每空2分,共20分) 1. 已知一颗二叉树的前序序列和中序序列分别为: ABCDEFG ; CBDEAFG ; 它的后序序列是__________;它的层次序列是___________. 2. 对8个节点的无向图,若确保其为连通图,至少需要___条边.若确保其为重连通图,至少需____条边. 3. 采用败者树进行K路归并时,所需工作空间至少为____个,选取一个当前最小关键字需进行____此比较. 4. 一颗含有15个关键字的4阶B树,其非叶节点数最少不能少于____个,最多可以为____个. 5. 高度为5的平衡二叉树;其节点数最多可以有____个;最少可以是____个. 程序阅读(共20分) 1. 对于正整数n,输出其和等于n且满足以下限制条件的所有正整数的和式, 组成和式的数字自左至右构成一个非递增的序列.如 n = 4 , 程序输出为: 4 = 4 4 = 3 + 1 4 = 2 + 2 4 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1 test 是实现该功能的C程序段,请将未完成的部分补足,使之完整. Test函数为一递归函数,参数n为被分解和式的数, k为当前的分解深度.算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数) 存于数组a[ ]中.当其中一个分解已不再需要进一步进行时,即找到一个解,将存于 a[ ] 中的一个完整和式的和数输出.当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用test函数. #define MAXN 100 int a[MAXN]; test(int n, int k) { int i,j; for( j= ; j >= 1 ; j – – ) (3分) { a[k]=j; if ( ) (3分) { printf("%d = %d",a[0],a[1]); for ( i = 2; i <= k; i ++ ) printf(" + %d",a[i]); printf("\n"); } else test( ; k+1); (4分) } } main() { test(4,1); } 2. 设输入为整数数组A[1..n],其中1≤ A[i] ≤ k (1≤ i ≤ n);输出数组为B[1..n]; C[1..k]是临时工作空间;阅读下属算法后,回答下列问题: proc Demo(A,B,k) { for i:=1 to k do C[i]:=0; for j:=1 to n do C[A[j]]:= C[A[j]]+1; for i:=2 to k do C[i]:= C[i]+ C[i-1]; for j:=n downto 1 do{ B[C[A[j]]]:=A[j]; C[A[j]]:=C[A[j]]-1; } } 当标号(2)行的循环执行完后,C[i] ( 1≤ i ≤ n )的值有何意义? (3分) 当标号(3) 行的循环执行完后,C[i] ( 1≤ i ≤ n )的值有何意义? (3分) 算法执行后,B的内容有和特点? 当k=O(n)时,算法的时间复杂度是多少? 程序设计 1. 已知一个n×n的上三角矩阵a的上三角元素已按行主序连续存放在数组b中.请设计一个函数trans将b中元素按列主序连续存放至数组c中. (15分) 例:设n=5;  b=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) c=(1,2,6,3,7,10,14,8,11,13,5,9,12,14,15) 2. 设二叉排序树的存储结构为: type bitree = ^ node; node = record key:keytype; size:int; lchild,rchild:bitree end; 其中一个节点x的size域的值为以x为根的子树中节点的总数(包括x本身). 例如下一颗二叉排序树:每个节点图示为 若设该二叉排序树高为h,试写一个时间为O(h)的算法Select(T:bitree;i:int), 要求该算法返回一个指向二叉排序树T的中根序列里第i个最小元素的指 针.若i值非法,返回空指针. 例如对上图调用Select(T,7)时返回指向key为16的节点指针. 注意:不允许用中序遍历的方法完成.需要利用节点的Size信息. (15分) 3. 请写一个算法求无环连通图T的中心. (提示:首先将T中度为1的节点(叶子)删去得到子图T1,然后再删去T的叶子,…如此反复,直到某个子图Tk为止.Tk或者只含一个节点,它即是T的唯一中心;或者Tk含有两个节点,它们都是T的中心).若图有两个中心,求出任意一个即可. 存储结构均采用邻接表.在顶点表中可加一个度数域. data degree firstadj           ┇        (20分)