2022年期末考试试题答案 .pdf

《2022年期末考试试题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年期末考试试题答案 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 / 9 得 分数据结构试卷（开卷）（电信系本科2002 级 2003年 12 月）题号一二三总分题分32 38 30 100 得分一、回答下列问题 ( 每题 4 分，共 32 分) 1. 对于一个有10000 个结点的二叉树，树叶最多有多少个？最少有多少个？答： 最多是完全二叉树的形态，即5000 个叶子；最少是单支树的形态，即1 个叶子。2. 已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和 DGEBHFCA ，则该二叉树的前序序列是什么？答：是： ABDEGCFH 3. 设有1000 个无序的元素，需排出前10 个最大（小）的元素，你认为采用哪种排序方法最快？为什么？答：用

2、锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n) ；即 O（1000log21000 ） =O(10000) 锦标赛排序的准确比较次数为：堆排序的准确比较次数为：若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+ n-10）=10n-55=10000-55=9945 （次）4. 在 KMP 算法中，已知模式串为ADABCADADA ，请写出模式串的nextj函数值。答： 0112112343 5. 中序遍历的递归算法平均空间复杂度为多少？答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n) 姓名班级精

3、选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页2 / 9 得 分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 （注意要按振荡式逼近算法实现） 堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而

4、且要排成小根堆！初始堆序列为：10，24，12，79，49， 27，13，36，36*, 70, 100, 96无序堆有序初始堆7. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），设哈希函数H（key） key MOD 13 。请写出用线性探测法处理冲突构造所得的哈希表。答：0 1 2 3 4 5 6 7 8 9 10 11 12 49 40 17 31 32 30 46 47 10 24 63 8. 算法复杂度O（1）的含义是什么？答：它表示与输入的元素规模无关，是一个常数（但不一定是1）。或：它表示该算法执行时耗费时间的长短或占用

5、辅助空间的多少与元素个数n 无关，若能达到这样的时间效率或空间效率，将是最理想的算法。二、综合题（ 4 小题，共 38 分）1.下图为某无向图的邻接表，按教材算法7.5 和 7.6 分别写出深度优先搜索和广度优先搜索的结果，并画出逻辑结构图。 (10分) 24 79 13 36 70 96 12 10 36*49 100 27 10 24 12 79 49 27 13 36 36*70 100 96 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页3 / 9 A 5 B 3 7 C 2 6 7 D E 1 F 3 G 2 3 H

6、9 10 I 8 J 8 答：深度优先搜索（DFS ）结果为： AEBCFGDHIJ 广度优先搜索（BFS ）结果为： AEBCGFDHIJ 这是有着4 个连通分量的非连通图。A E B C F G H I D J 2.设 AH8个字符出现的概率为:=0.10, 0.16,0.01, 0.02, 0.29, 0.10, 0.07, 0.25, 设计最优二进制码并计算平均码长。如果设计最优三进制编码（即可用0,1,2三种符号进行编码），画出最优三叉树并计算平均码长。 (10分 ) 答：最优二进制编码不惟一，但WPL惟一。1 2 3 4 5 6 7 8 9 10 0 1.00 0 0.450.55

7、0 0.20 0.25 0.26 0.290 0.10 0.100 0.03 0.07 A0.100.160.010.02A：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 页，共 9 页4 / 9 对三进制编码，由于总共有8 个字符， 8%3=2,故第一次构建最

8、优树只有2 个结点，则最优三叉树为3.给定一个由n 个关键字不同的记录构成的序列，你能否用2n-3 次比较找出n 个元素中的最大值和最小值？如果有，请描述你的方法。最快需多少次比较？（无需写算法） (8 分)答：可以实现。选用锦标赛算法。两两元素比较，淘汰较小的，形如一棵二叉树。树根为最大值（此时用掉 n-1 次比较 ？）。而最小者一定位于首次被淘汰之列。故只有 n/2 个。一共需n-1+ n/2 次比较。4. 分析下面算法中l 和 h变量表示什么含义？初始调用时，l 和 h应取什么值？其中p为指向二叉树的根结点，如果去掉形参中的“&”符号，会得到什么结果？ (10 分)解：依分析，l、h表示

9、二叉树的层次数和深度。开始调用时，应为ABC （p, 0, 0 ） 1.00 0.550.45 0.26 0.29 0.20 0.25 0.10 0.16 0.03 0.070.100.100.010.02A：100 B: 001 C: 00000 D: 00001 E: 01 F: 101 G: 0001 H: 11 平均码长仍为：PiWi=2.59 Void ABC(Bitree p, int l, int &h) if p NIL then l=l+1。 if lh then h=l。ABC(p-Lchild, l,h)。ABC(p-Rchild, l,h)。 1.00 0 1 2 0.

10、29 0.51 0 0.20 2 0 0.03 0.070.100.10 0.16 0.250.010.02编码为：A：02 B: 21 C: 000 D: 001 E: 1 F: 20 G: 01 H: 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.74 此题含义是：求树的深度（h）但求解方法是从根开始计算层次。反而比从叶子往上计算要简单。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页5 / 9 得 分去掉形参中的

11、“&”号，则上次计算的结果不能正确返回。故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) 。 /遍历当前结点左子

12、树rightdep=BTreeDepth(BT-right) 。 /遍历当前结点右子树if( leftdeprightdep)return(leftdep+1)。 /从叶子计数 else return(rightdep+1) 。 /BTreeDepth三、算法设计题（每题10 分，共 30 分）1. 试用 C 或类 C 语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。解：void SortA(sqlist &L) int i=0, zerosum =0 。if(L.length=0) return(0) 。 /空表else fo

13、r( i=1 。 i=L.length 。 i+) if (L.vi0) L.vi- zerosum= L.vi 。 /非空表时特别浪费！zerosum+。 while( zerosum!=0)L.vi = =0。 zerosum- /表的后部补0 return(ok) 以上算法在非空表时特别浪费！解： void SortA(sqlist &L) int i=0,zerosum =0 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页6 / 9 if(L.length= =0) return(0) 。 /空表则不执行while(i

14、=L.length&(L.vi 0) i+ 。 /非空表则不移动if(iL.length) return(ok)。elsei+ 。 zerosum+。/若有零元素则统计和移动for( i 。 i=L.length 。 i+)if ( L.vi = =0) zerosum+ 。else L.vi- zerosum= L.vi 。 。/非零元素顺序前移while( zerosum!=0)L.vi = =0。 zerosum- /表的后部补0 return(ok)解 2：void SortA(sqlist &L) int i=0,zerosum =0 。if(L.length= =0) return

15、(0) 。 /空表则不执行while(i=L.length&(L.vi 0) i+ 。 /非空表则不移动if(iL.length) return(ok)。if(iL.length) return(ok)。i+ 。 zerosum+。/一定有零元素for( i。 i=L.length。 i+)if (L.vi0) L.vi- zerosum= L.vi。zerosum+。 while( zerosum!=0)L.vi = =0。 zerosum- /表的后部补0 return(ok)2. 试编写一个算法， 判断一给定的整型数组an 是不是一个堆。解：void SortA(sqlist &A, i

16、nt n) if(n=0) return(0)。 /空表if (a1a2) for( i=1 。 ia2*i| aia2*i+1)return(-1)。return(minleap) 。else for( i=1 。 i=n/2 。 i+) if (aia2*i| ailchild) 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=count0,

17、i=1 。 h。 i+) if(countimaxn) maxn=counti 。 /求出哪一层结点数最多 return (h*maxn) / Width 附加题：（ 15 分）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页8 / 9 设 p、t 分别表示两棵没有度为1 的结点的二叉树。设计一种算法，找出p 和 t 中最大的同构子树并分析算法的时间复杂度（无需写出算法，描述思路即可）。注：“同构”是指两个二叉树不仅结点数相同、并且它们的左右子树之间的关系也相同，但各结点的数据值可以不同。“最大的同构子树”即结点最多的同构子树。解

18、： 我们把一棵二叉树用树描述符来表示，则问题会变得容易解决。所谓树描述符，即对每个结点按二叉树先序遍历并输出结点的度。例如左边二叉树的描述符为202202000. 在此描述符法二： 若不用辅助数组，不用层数分量也可以，关键在于如何区别层与层。有两种方法：一、通过比较指针判断是否到达新的一层的开始。二、通过比较指针判断是否到达当前层的末尾. 由于方法一对新的一层的开始点不易确定，比较次数要多于第二种，因此推荐第二种。对任意种类的树都适用，二叉树类似可得。算法如下：/- / TreeWidth 求树的宽度/ 不用辅助数组，不用层数分量/ 思路：/ 1.以两个整型变量存宽度，一个表示当前层的节点数，

19、一个表示当前已知最大宽度，当遍历完一层后立即判断两者大小，保留大者。/ 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(!QueueEmp

20、ty(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) 。 /读出队尾元素，注意不是出队!/既已到本层末尾，又已将其孩子入队(若有的话 )，则队尾元素 必为下一层的最末元素

21、 return iMaxCount 。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页9 / 9 中，如果一个子串的字符数等于此子串中每个数字之和加1，则此子串一定是一个子树。如上面的字符串中，2202000 是一个子树，因为他有7 个字符，每个字符数字和为2+2+2=6. 同理， 20200,200也是子树。问题转化为两个字符串中寻找满足上述条件的最长公共子串。最长公共子串的算法已有（见习题），只需在此算法中加上判断此子串是否是一个子树的条件即可。判断一个子串是否为一个子树的复杂度为O（ n）,n 为字符串长度。由于求最长公共子串的复杂度为O(mn) ，m、n 分别为 p 和 t 的结点数，判子串是否为子树的过程可以和求最长公共子串相结合，即在求最长公共子串中完成。则求最大同构子树的复杂度为O(mn)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页