（电信系本科2002级 2003年12月）
姓名 班级 题号 题分 得分
得 分 一 32 二 38 三 30 总分 100 一、回答下列问题 (每题4分，共32分)
1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？
答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。
2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？
答：是：ABDEGCFH
3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？ 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果， 时间效率为O(nlog2n)； 即O（1000log21000）=O(10000)
锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089 堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089
若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）
4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。 答：
5. 中序遍历的递归算法平均空间复杂度为多少？
答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n)
6. 欲将无序序列（24, 79, 13, 36, 70, 96, 12, 10, 36*, 49, 100, 27）中的关键码按
升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆。
答：①快速排序第一趟排序的结果序列为：10， 12， 13， [24]， 70， 96, 36, 79, 36*, 49, 100, 27 （注意要按振荡式逼近算法实现）
② 堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排
24 79 13 36 70 96 12 10 36*49 100 27 成小根堆！ 初始堆序列为： 10，24，12，79，49，27，13，36，36*, 70, 100, 96 无序堆 有序初始堆
10 24 12 7. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 6349） 79 40 ，49 ， 27 ，设哈希函数 13 H（key）＝key MOD 13。请写出用线性探测法处理冲突构造所得的哈希表。 36 36*70 100 96 答： 0 49
1 40 2 3 4 17 5 31 6 32 7 30 8 46 9 47 10 10 11 24 12 63 8. 算法复杂度O（1）的含义是什么？
答：它表示与输入的元素规模无关，是一个常数（但不一定是1）。
或：它表示该算法执行时耗费时间的长短或占用辅助空间的多少与元素个数n无关，若能达到这样的时间效率或空间效率，将是最理想的算法。
得 分 二、综合题（4小题，共38分）
1. 下图为某无向图的邻接表，按教材算法7.5和7.6分别写出深度优先搜索和广度优先搜索的结果，并
画出逻辑结构图。 (10分)
1 2 3 4 5 A C D ^ 5 3 2 ^ 7 6 ^ 7 2 ^ B 6 7 E F G H I J
1 3 2 9 8 8 ^ ^ ^ ^
3
^
10 ^ 答：深度优先搜索（DFS）结果为：AEBCFGDHIJ 广度优先搜索（BFS）结果为：AEBCGFDHIJ 这是有着4个连通分量的非连通图。
A E
B C F
G H I
D J
2. 设A～H 8个字符出现的概率为: ={0.10, 0.16, 0.01, 0.02, 0.29, 0.10, 0.07, 0.25},
设计最优二进制码并计算平均码长。如果设计最优三进制编码（即可用0,1,2三种符号进行编码），画出最优三叉树并计算平均码长。 (10分) 答：最优二进制编码不惟一，但WPL惟一。
0 1.00 0 0.45 0.55 0 0.20 0.25 0.26 0.29 0 0.10 0.10 0 0.03 0.07 A 0.10 0.16 0.01 0.02 若按教材算法，合并规律应当如下： A：001 B: 101 C: 00000 D: 00001 E: 11 F: 100 G: 0001 H: 01 平均码长为： ΣPiWi= =3×（0.1＋0.16＋0.1） ＋5×（0.01+0.02） +2×（0.29+0.25） +4×0.07 =2.59 3
对三进制编码，由于总共有8个字符，8%3=2,故第一次构建最优树只有2个结点，则最优三叉树为
1.00 0 1 2 0.29 0.51 0 0.20 2 0 0.03 0.07 0.10 0.10 0.16 0.25 0.01 0.02 1.00 0.55 0.45 平均码长为： 0.26 0.29 0.20 0.25 ΣPiWi=1×0.29+2×(0.1+0.16+0.10+0.07+0.25)+ 0.10 0.16 3×(0.01+0.02)=0.29+1.36+0.09=1.74 0.03 0.07 0.10 0.10 0.01 0.02 A：100 B: 001 C: 00000 D: 00001 E: 01 F: 101 G: 0001 H: 11 编码为： A：02 B: 21 C: 000 D: 001 E: 1 F: 20 G: 01 平均码长仍为： H: 22 ΣPiWi=2.59
3. 给定一个由n个关键字不同的记录构成的序列，你能否用2n-3次比较找出n个元素中的最大值和最小
值？如果有，请描述你的方法。最快需多少次比较？（无需写算法） (8分) 答：可以实现。选用锦标赛算法。两两元素比较，淘汰较小的，形如一棵二叉树。树根为最大值（此时用掉n-1次比较？）。而最小者一定位于首次被淘汰之列。故只有 n/2个。一共需n-1+ n/2次比较。
4. 分析下面算法中l和h变量表示什么含义？初始调用时，l和h应取什么值？其中p为指
向二叉树的根结点，如果去掉形参中的“&”符号，会得到什么结果？ (10分)
Void ABC(Bitree p, int l, int &h) { if p≠NIL then {l=l+1; if l>h then h=l; ABC(p->Lchild, l,h); ABC(p->Rchild, l,h); } } 此题含义是：求树的深度（h） 但求解方法是从根开始计算层次。 反而比从叶子往上计算要简单。 解：依分析，l、h表示二叉树的层次数和深度。(l之前千万不能加&符号，否则不通) 开始调用时，应为ABC（p, 0, 0）
4
去掉形参中的“&”号，则上次计算的结果不能正确返回。故h不变，得不到正确结果。
这里的int &h应当理解为push形参，每次返回就要return 实参。所以l和h其实是每一层当前的状态。L代表当前结点所在的层数（从根结点计算起）；而h代表当前结点所在的深度。 附：教材(习题集？)求深度的函数如下：
int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针 {int leftdep, rightdep; //设左右两个深度/层次计数器 if(BT==NULL) return(0); //当前结点指针为空则立即返回else { leftdep= BTreeDepth(BT->left); //遍历当前结点左子树 rightdep=BTreeDepth(BT->right); //遍历当前结点右子树 if( leftdep>rightdep)return(leftdep+1); //从叶子计数 else return(rightdep+1); }
} //BTreeDepth
得 分 三、 算法设计题（每题10分，共30分）
顺序表的存储结构为： typedef struct{ 1. 试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所Elemtype v[ ]; 有零元素向表尾集中，其他元素则顺序向表头方向集中。 int length; 解： void SortA(sqlist &L) }L; { int i=0, zerosum =0; 算法的核心部分为：void SortA(sqlist &L) if(L.length==0) return(0); //空表 { int i=0, zerosum =0; else { if(L.length==0) return(0); //空表 for( i=1; i<=L.length; i++) else { {if (L.v[i]<>0) L.v[i- zerosum]= L.v[i]; for( i=1; i<=L.length; i++) else ? zerosum++; {if (L.v[i]<>0) L.v[i- zerosum]= L.v[i]; } else zerosum++;} } for(i=i-zerosum+1; i<=L.length; i++)
5
2. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。 解：提示：堆的定义是：ki return(minleap) }; else { for( i=1; i<=n/2; i++) if (a[i] 法一：要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。 typedef struct { BTNode node; int layer; //layer是结点所在层数 } BTNRecord, r ; int Width(Bitree T ){ //求树宽 int count[ ]; //增开count向量，存放各层对应的结点数 InitQueue(Q); //队列初始化，Q的元素为BTNRecord类型 EnQueue(Q,{T, 0}); //根结点入队, 0 表示count[0]，下标值 while(!QueueEmpty(Q)) { DeQueue(Q, r); //结点出队 count[r.layer]++; //出队时再把结点对应层的计数器加 if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按层序入队时要随时标注结点所在层号 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) 6 if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多 return (h*maxn)} // Width 7 法二：若不用辅助数组，不用层数分量也可以，关键在于如何区别层与层。有两种方法： 一、通过比较指针判断是否到达新的一层的开始; 二、通过比较指针判断是否到达当前层的末尾. 由于方法一对新的一层的开始点不易确定，比较次数要多于第二种，因此推荐第二种。 对任意种类的树都适用，二叉树类似可得。 算法如下： //------------------------------------------------------------------------------------------ // TreeWidth 求树的宽度 // 不用辅助数组，不用层数分量 // 思路： // // 1.以两个整型变量存宽度，一个表示当前层的节点数，一个表示当前已知最大宽度，当遍历完一层后立即判断两者大小，保留大者。 2.通过比较指针判断是否到达本层的末尾，以确定层与层间的关系。 //------------------------------------------------------------------------------------------- int TreeWidth(TreeNode * T) { int iMaxCount=0,iRecCount=0;//iRecCount当前层的节点数,iMaxCount当前已知最大宽度 TreeNode * pP=T,* pLastChild=T;//pP指向当前节点,pFirstChild指向本层最末节点 InitQueue(Q);//队列初始化，Q的元素为TreeNode*类型 EnQueue(Q,T);//根结点入队 while(!QueueEmpty(Q)) { DeQueue(Q,pP);//结点出队 iRecCount++;//出队时再把结点所在层的计数器加1 if(hasChild(pP)) EnQueue(Q,pP->Child);//有孩子则孩子入队 if(pP=pLastChild)//若到达本层的末尾 {//先决定iMaxCount，再重置iRecCount //求繁茂度不能清零此变量。 iMaxCount=max(iMaxCount,iRecCount); iRecCount=0; QueueTail(Q,pLastChild); //读出队尾元素，注意不是出队!!! //既已到本层末尾，又已将其孩子入队(若有的话)，则队尾元素必为下一层的最末元素 } } return iMaxCount; } 附加题：（15分） 设p、t分别表示两棵没有度为1 的结点的二叉树。设计一种算法，找出p和t中最大的同构子树并分析算法的时间复杂度（无需写出算法，描述思路即可）。 注：“同构”是指两个二叉树不仅结点数相同、并且它们的左右子树之间的关系也相同，但各结点的数据值可以不同。 8 “最大的同构子树”即结点最多的同构子树。 解： 我们把一棵二叉树用树描述符来表示，则问题会变得容易解决。所谓树描述符，即对每个结点按二 叉树先序遍历并输出结点的度。例如左边二叉树的描述符为.在此描述符中，如果一个子串的字符数等于此子串中每个数字之和加1，则此子串一定是一个子树。 如上面的字符串中，是一个子树，因为他有7个字符，每个字符数字和为2+2+2=6. 同理，20200,200也是子树。 问题转化为两个字符串中寻找满足上述条件的最长公共子串。 最长公共子串的算法已有（见习题），只需在此算法中加上判断此子串是否是一个子树的条件即可。 判断一个子串是否为一个子树的复杂度为O（n）,n为字符串长度。 由于求最长公共子串的复杂度为O(mn)，m、n分别为p和t的结点数，判子串是否为子树的过程可以和求最长公共子串相结合，即在求最长公共子串中完成。 则求最大同构子树的复杂度为O(mn)。 9 因篇幅问题不能全部显示，请点此查看更多更全内容