02级期末考试试题答案(草稿)

1得分《数据结构》试题（开卷）（电信系本科2002级2003年12月）题号一二三总分题分323830100得分一、回答下列问题(每题4分，共32分)1.对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？答：最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？答：是：ABDEGCFH3.设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)；即O（1000log21000）=O(10000)锦标赛排序的准确比较次数为：堆排序的准确比较次数为：若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4.在KMP算法中，已知模式串为ADABCADADA，请写出模式串的next[j]函数值。答：01121123435.中序遍历的递归算法平均空间复杂度为多少？答：要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为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（注意要按振荡式逼近算法实现）②堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！初始堆序列为：10，24，12，79，49，27，13，36，36*,70,100,96无序堆有序初始堆247913367096121036*4910027102412794927133636*7010096姓名班级2得分7.已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝keyMOD13。请写出用线性探测法处理冲突构造所得的哈希表。答：012345678910111249401731323046471024638.算法复杂度O（1）的含义是什么？答：它表示与输入的元素规模无关，是一个常数（但不一定是1）。或：它表示该算法执行时耗费时间的长短或占用辅助空间的多少与元素个数n无关，若能达到这样的时间效率或空间效率，将是最理想的算法。二、综合题（4小题，共38分）1.下图为某无向图的邻接表，按教材算法7.5和7.6分别写出深度优先搜索和广度优先搜索的结果，并画出逻辑结构图。(10分)A5^B37^C267^D^E1^F3^G23^H910^I8^J8^答：深度优先搜索（DFS）结果为：AEBCFGDHIJ广度优先搜索（BFS）结果为：AEBCGFDHIJ这是有着4个连通分量的非连通图。AEBCFGHIDJ1234567891032.设A～H8个字符出现的概率为:={0.10,0.16,0.01,0.02,0.29,0.10,0.07,0.25},设计最优二进制码并计算平均码长。如果设计最优三进制编码（即可用0,1,2三种符号进行编码），画出最优三叉树并计算平均码长。(10分)答：最优二进制编码不惟一，但WPL惟一。对三进制编码，由于总共有8个字符，8%3=2,故第一次构建最优树只有2个结点，则最优三叉树为3.给定一个由n个关键字不同的记录构成的序列，你能否用2n-3次比较找出n个元素中的最大值和最小值？如果有，请描述你的方法。最快需多少次比较？（无需写算法）(8分)答：可以实现。选用锦标赛算法。两两元素比较，淘汰较小的，形如一棵二叉树。树根为最大值（此时用掉n-1次比较？）。而最小者一定位于首次被淘汰之列。故只有n/2个。一共需n-1+n/2次比较。01.0000.450.5500.200.250.260.2900.100.1000.030.07A0.100.160.010.02A：001B:101C:00000D:00001E:11F:100G:0001H:011.000.550.450.260.290.200.250.100.160.030.070.100.100.010.02平均码长为：ΣPiWi==3×（0.1＋0.16＋0.1）＋5×（0.01+0.02）+2×（0.29+0.25）+4×0.07=2.59A：100B:001C:00000D:00001E:01F:101G:0001H:11平均码长仍为：ΣPiWi=2.59若按教材算法，合并规律应当如下：1.000120.290.5100.20200.030.070.100.100.160.250.010.02编码为：A：02B:21C:000D:001E:1F:20G:01H:22平均码长为：ΣPiWi=1×0.29+2×(0.1+0.16+0.10+0.07+0.25)+3×(0.01+0.02)=0.29+1.36+0.09=1.744得分4.分析下面算法中l和h变量表示什么含义？初始调用时，l和h应取什么值？其中p为指向二叉树的根结点，如果去掉形参中的“&”符号，会得到什么结果？(10分)解：依分析，l、h表示二叉树的层次数和深度。开始调用时，应为ABC（p,0,0）去掉形参中的“&”号，则上次计算的结果不能正确返回。故h不变，得不到正确结果。这里的int&h应当理解为push形参，每次返回就要return实参。所以l和h其实是每一层当前的状态。L代表当前结点所在的层数（从根结点计算起）；而h代表当前结点所在的深度。附：教材求深度的函数如下：intBTreeDepth(Btree*BT)//*BT为二叉树某结点的指针{intleftdep,rightdep;//设左右两个深度/层次计数器if(BT==NULL)return(0);//当前结点指针为空则立即返回else{leftdep=BTreeDepth(BT-left);//遍历当前结点左子树rightdep=BTreeDepth(BT-right);//遍历当前结点右子树if(leftdeprightdep)return(leftdep+1);//从叶子计数elsereturn(rightdep+1);}}//BTreeDepth三、算法设计题（每题10分，共30分）1.试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。解：voidSortA(sqlist&L){inti=0,zerosum=0;if(L.length==0)return(0);//空表else{for(i=1;i=L.length;i++){if(L.v[i]0)L.v[i-zerosum]=L.v[i];//非空表时特别浪费！VoidABC(Bitreep,intl,int&h){ifp≠NILthen{l=l+1;iflhthenh=l;ABC(p-Lchild,l,h);ABC(p-Rchild,l,h);}}此题含义是：求树的深度（h）但求解方法是从根开始计算层次。反而比从叶子往上计算要简单。5zerosum++;}while(zerosum!=0){L.v[i]==0;zerosum--}//表的后部补0}return(ok)}以上算法在非空表时特别浪费！解：voidSortA(sqlist&L){inti=0,zerosum=0;if(L.length==0)return(0);//空表则不执行while(i=L.length&&(L.v[i]0)i++;//非空表则不移动if(iL.length)return(ok);else{i++;zerosum++;//若有零元素则统计和移动for(i;i=L.length;i++){if(L.v[i]==0)zerosum++;elseL.v[i-zerosum]=L.v[i];};//非零元素顺序前移while(zerosum!=0){L.v[i]==0;zerosum--}//表的后部补0}return(ok)解2：voidSortA(sqlist&L){inti=0,zerosum=0;if(L.length==0)return(0);//空表则不执行while(i=L.length&&(L.v[i]0)i++;//非空表则不移动if(iL.length)return(ok);if(iL.length)return(ok);i++;zerosum++;//一定有零元素for(i;i=L.length;i++){if(L.v[i]0)L.v[i-zerosum]=L.v[i];zerosum++;}while(zerosum!=0){L.v[i]==0;zerosum--}//表的后部补0}return(ok)2.试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。解：voidSortA(sqlist&A,intn){if(n==0)return(0);//空表if(a[1]a[2]){for(i=1;i=n/2;i++)if(a[i]a[2*i]||a[i]a[2*i+1])return(-1);return(minleap)};else{for(i=1;i=n/2;i++)if(a[i]a[2*i]||a[i]a[2*i+1])return(-1);return(“maxleap”)};}63.一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。法一：要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。typedefstruct{BTNodenode;intlayer;//layer是结点所在层数}BTNRecord,r;intWidth(BitreeT){//求树宽intcount[];//增开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++)if(count[i]maxn)maxn=count[i];//求出哪一层结点数最多return(h*maxn)}//Width7附加题：（15分）设p、t分别表示两棵没有度为1的结点的二叉树。设计一种算法，找出p和t中最大的同构子树并分析算法的时间复杂度（无需写出算法，描述思路即可）。注：“同构”是指两个二叉树不仅结点数相同、并且它们的左右子树之间的关系也相同，但各结点的数据值可以不同。法二：若不用辅助数组，不用层数分量也可以，关键在于如何区别层与层。有两种方法：一、通过比较指针判断是否到达新的一层的开始;二、通过比较指针判断是否到达当前层的末尾.由于方法一对新的一层的开始点不易确定，比较次数要多于第二种，因此推荐第二种。对任意种类的树都适用，二叉树类似可得。算法如下：//-----------------------------------