一九九六年招收硕士学位研究生入学考试试题 试题名称:程序设计 单项选择: (20分) 具有几个节点的完全二叉树的深度是:_____. 1)  2)  + 1 3)  4)  – 1 用单循环链表表示队列,正确的说法是:______ 可设一个头指针使入队、出队都方便 可设一个尾指针使入队、出队都方便 必须设头、尾指针才能使入队、出队都方便; 无论如何,只可能使入队方便. 对无向图而言,同一条边在邻接表中用两个节点表示而在邻接多重表中只用一个节点表示,因此邻接多重表所需存储量比邻接表______. 1) 少一半 2) 多,但差异不大 3) 少,但差异不大 一个哈希函数被认为是“好的”,如果它满足条件________. 1) 哈希地址分布均匀 2) 保证不产生冲突 3) 所有哈希地址在表长范围内 4) 满足 2) 和 3) ISAM文件和VSAM文件属于___________. 1) 索引非顺序文件 2) 索引顺序文件 3) 顺序文件 4) 散列文件 在下述排序算法中_____算法是稳定的排序算法. 1) 希尔排序 2) 冒泡排序 3) 快速排序 平衡二叉树中,若某个节点在左、右子节点的平衡因子为零,则该节点的平衡因子也一定是零,这种说法______. 1) 不正确 2) 正确 在下属三种排序算法中,所需辅助存储量最多的是_____,所需存储量最少的是_______,平均速度最快的是______. 1) 堆排序 2) 快速排序 3) 归并排序 问答题(25分) 已知某电文中共出现10种不同的字母,各个字母出现的频率分别为A:8, B:5, C:3, D:2, E:7, F:23, G:9, H:15, I:3, J:35 ,现在对这段电文用三进制进行编码(即码字由0,1,2组成),问电文编码总长度最少有多少位?并画出图 A是一个三对角矩阵,行数与列数相等,用压缩存储的方法将其压缩存储到一维的数组SA[ 1 .. 3n – 2 ]中(按行序顺序存储),则SA[ k ]对应的矩阵元素的下标为: 行值 i = ________, 列值 j = _______.反过来,若知道A中元素的下标i , j ,则其存储位置 k=________.(写出表达式) 设A是一个栈,栈中共有n各元素,依次为: ,栈顶元素为,B是一个循环队列,队列中n各元素依次为,队头元素为, A、B均采用顺序存储结构且存储空间足够大,现要将栈中元素全部移到队列中,使得队列中元素与栈中元素交替排列,即B中元素为,问至少需要多少次基本操作才能完成上述工作,请写出具体步骤(要求除A、B外所用的其他附加存储量为1,每次出栈、入栈、出队列、入队列均看作一次基本操作). 试为下列二叉树建立后序线索,画出相应的后序线索二叉树. 算法描述(15分) 以二叉链表作存储结构,编写按层次顺序(从根节点开始)遍历二叉树的算法. 阅读下列程序,并回答:下列程序是否正确?为什么?如何修改? (5分) 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() 和 nd() . 函数 rd() 采用递归解法,它有两个参数 a 和 k . 其意义分别是被分解和式的数 n ,及当前第 k 深度分解.算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数) 存于数组a[ ]中.当其中一个分解已不再需要进一步分解时,即找到一个解,将存于数组 a[ ] 中的一个完整和式的和数输出.当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用分解和式函数. 函数 nd() 以要分解的数为参数,另开设一个数组r[ ],用于存储当前还未分解的余数.在求一个解的第 k 步时,a[k]为第k个和数,r[k]为相应的余数.当找到一个分解后(此步r[k]等于0,给出解,并做回溯处理,从当前k退回到第一个不为1的和数,将其减1,并将其余数加1,准备去找另一个解;否则,生成下一步的分解和数与余数.(15分) 答: 1) ________________ 2) _________________ 3) ________________ 4) _________________ 5) ________________ 6) _________________ [程序] #define MAXN 100 int a[MAXN], r[MAXN]; rd(int n, int k) { int j,i; for( j= ① ; j >= 1 ; j – – ) { a[k]=j; if ( ② ) { printf("%d = %d",a[0],a[1]); for ( i = 2; i <= k; i ++ ) printf(" + %d",a[i]); printf("\n"); } else ③ ; } } nd(int n) { int i,k; k=0; r[0]=n; do { if ( ④ ) { printf("%d = %d",a[0],a[1]); for ( i=2; i <= k; i + +) printf(" + %d",a[i]); printf("\n"); while ( k > 0 && ⑤ ) k – – ; if ( k > 0)　{ a[k] – – ; r[k] + + ; } } else { a[k+1] = ⑥ ; r[k+1] = r[k] – a[k+1]; k + +; } /* else */ } while ( k > 0 ); } int test_data[] = { 3, 4, 5 }; main() { int i; for ( i=0; i < sizeof test_data/sizeof (int) ; i ++) { a[0] = test_data[i]; rd(test_data[i],1); printf("\n___________________\n\n"); nd(test_data[i]); printf("\n___________________\n\n"); } } 设计一个程序读入一个字符串,统计该字符串中出现的字符及其次数,然后仪表的形式输出结果.要求用一个二叉树来保存处理结果,字符串中的每个不同的字符用数中不同的节点描述,每个节点包含四个域,格式为: 字符 该字符的出现次数 指向ASCII码小于该字符的左子树指针 指向ASCII码小于该字符的右子树指针 因此程序的功能是依次从输入字符串中取出一个字符,把它们插入到树中(新出现字符)或修改原树中相应节点的“出现次数”域(已出现字符). (20分)