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

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

1、精选学习资料 - - - - - - - - - 数据结构试卷（开卷）姓名题号（电信系本科2002 级 2003年 12 月）三总分班级二一题分32 38 30 100 得分得 分1. 对于一个有一、回答以下问题 每题 4 分,共 32 分 10000 个结点的二叉树,树叶最多有多少个？最少有多少个？答： 最多是完全二叉树的形状,即 5000 个叶子；最少是单支树的形状,即 1 个叶子；2. 已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF 和 DGEBHFCA ,就该二叉树的前序序列是什么？答：是： ABDEGCFH 3. 设有1000 个无序的元素,需排出前10 个最大（小）的元

2、素,你认为采纳哪种排序方法最快？为什么？答：用锦标赛排序或堆排序很合适,由于不必等全部元素排完就能得到所需结果,时间效率为 Onlog2n ；即 O（1000log 21000 ） =O10000 锦标赛排序的精确比较次数为：堆排序的精确比较次数为：如用冒泡排序也较快,最多耗费比较次数为（n-1+n-2+ n-10）=10n-55=10000-55=9945 （次）4. 在 KMP 算法中,已知模式串为ADABCADADA ,请写出模式串的nextj函数值；答： 0112112343 5. 中序遍历的递归算法平均空间复杂度为多少？答： 要考虑递归时占用了栈空间,但递归次数最多不超过树的高度,所

3、以空间复杂度为 Olog2n 1 / 9 名师归纳总结 - - - - - - -第 1 页,共 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、结点开头,自下而上调整 ,而且要排 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 79 49 27 13 7. 已知一组关键字为（36 36*70 100 96 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 3

5、2 30 46 47 10 24 63 8. 算法复杂度O （1）的含义是什么？答：它表示与输入的元素规模无关,是一个常数（但不肯定是 1）；或：它表示该算法执行时耗费时间的长短或占用帮助空间的多少与元素个数间效率或空间效率,将是最抱负的算法；得 分 二、综合题（ 4 小题,共 38 分）n 无关,如能达到这样的时1.下图为某无向图的邻接表,按教材算法7.5 和 7.6 分别写出深度优先搜寻和广度优先搜寻的结果,并画出规律结构图； 10分 2 / 9 名师归纳总结 - - - - - - -第 2 页,共 9 页精选学习资料 - - - - - - - - - 1 A 5 7 7 B 3 2

6、C 2 6 3 D 4 E 1 3 F 3 5 G 2 6 H 9 10 7 I 8 8 J 8 9 答：深度优先搜寻（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分 A：001 平均码长为：答：最优二进制编码不

7、惟一,但WPL惟一； 0 1.00 0 0.450.55B: 101 PiWi= 0 0.20 0.25 0.26 0.29C: 00000 =3 （ 0.1 0.16 0 0.10 0.10D: 00001 0.1）0 0.03 0.07 A0.100.16E: 11 5 （ 0.01+0.02）+2 （ 0.29+0.25）0.010.02F: 100 如按教材算法,合并规律应当如下：G: 0001 +4 0.07 H: 01 =2.59 3 / 9 名师归纳总结 - - - - - - -第 3 页,共 9 页精选学习资料 - - - - - - - - - 对三进制编码,由于总共有8

8、个字符, 8%3=2,故第一次构建最优树只有2 个结点,就最优三叉树为1.00 A：100 编码为： 0 1 2 A：02 0.29 0.51B: 21 0 0.20 2 C: 000 0 0.03 0.070.100.10 0.16 0.25D: 001 0.010.02E: 1 1.00 F: 20 平均码长为：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.10B: 001 G: 0

9、1 平均码长仍为：C: 00000 H: 22 PiWi=2.59 D: 00001 E: 01 0.010.02F: 101 G: 0001 H: 11 3.给定一个由n 个关键字不同的记录构成的序列,你能否用2n-3 次比较找出n 个元素中的最大值和最小值？假如有,请描述你的方法；最快需多少次比较？（无需写算法） 8 分答：可以实现；选用锦标赛算法；两两元素比较,剔除较小的,形如一棵二叉树；树根为最大值（此时用掉 n-1 次比较 ？）；而最小者肯定位于首次被剔除之列；故只有 n/2 个；一共需 n-1+ n/2 次比较；4. 分析下面算法中 l 和 h 变量表示什么含义？初始调用时,l 和

10、 h 应取什么值？其中 p 为指向二叉树的根结点,假如去掉形参中的“& ” 符号,会得到什么结果？ 10 分Void ABCBitree 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； 此题含义是：求树的深度（h）但求解方法是从根开头运算层次；反而比从叶子往上运算要简洁；解：依分析, l、h表示二叉树的层次数和深度；开头调用时,应为 ABC （p, 0, 0 ）4 / 9 名师归纳总结 - - - - - - -第 4 页,共 9 页精选学习资料 - - - -

11、 - - - - - 去掉形参中的“ &” 号,就上次运算的结果不能正确返回；故h不变,得不到正确结果；这里的int & h 应当懂得为push形参,每次返回就要return 实参；所以l 和 h 其实是每一层当前的状态；L代表当前结点所在的层数（从根结点运算起）；而附：教材求深度的函数如下：h 代表当前结点所在的深度；int BTreeDepthBtree *BT /*BT 为二叉树某结点的指针int leftdep, rightdep ； /设左右两个深度 /层次计数器ifBT=NULL return0； /当前结点指针为空就立刻返回 else leftdep= BTreeDepthBT-

12、left ； /遍历当前结点左子树rightdep=BTreeDepthBT-right ； /遍历当前结点右子树if leftdeprightdepreturnleftdep+1； /从叶子计数 else returnrightdep+1 ； /BTreeDepth得 分三、算法设计题（每题10 分,共 30 分）1. 试用 C 或类 C 语言编写一高效算法,将一次序储备的线性表（设元素均为整型量）中所有零元素向表尾集中,其他元素就次序向表头方向集中；解： void SortAsqlist &L int i=0, zerosum =0 ；ifL.length=0 return0 ； /空表

13、else for i=1 ； i=L.length ； i+ if L.vi0 L.v i- zerosum= L.vi ； /非空表时特殊铺张！zerosum+； while zerosum.=0L.vi = =0； zerosum- /表的后部补 0 returnok 以上算法在非空表时特殊铺张！解： void SortAsqlist &L int i=0,zerosum =0 ；5 / 9 名师归纳总结 - - - - - - -第 5 页,共 9 页精选学习资料 - - - - - - - - - ifL.length= =0 return0 ； /空表就不执行whilei=L.len

14、gth& L.vi 0 i+ ； /非空表就不移动 ifiL.length returnok；elsei+ ； zerosum+；/如有零元素就统计和移动 for i ； i=L.length ； i+ if L.vi = =0 zerosum+ ；else L.vi- zerosum= L.vi ； ；/非零元素次序前移 while zerosum.=0L.vi = =0； zerosum- /表的后部补 0 returnok解 2：void SortAsqlist &L int i=0,zerosum =0 ；ifL.length= =0 return0 ； /空表就不执行whilei=L

15、.length&L.vi 0 i+ ； /非空表就不移动ifiL.length returnok；ifiL.length returnok；i+ ； zerosum+ ；/肯定有零元素for i ； i=L.length； i+if L.vi0 L.vi- zerosum= L.vi；zerosum+； while zerosum.=0L.vi = =0； zerosum- /表的后部补 0 returnok2. 试编写一个算法, 判定一给定的整型数组 解： void SortAsqlist &A, int n ifn=0 return0； /空表 if a1a2 an 是不是一个堆； for

16、 i=1 ； ia2*i| aia2*i+1return-1；returnminleap ；else for i=1 ； i=n/2 ； i+ if aia2*i| ailchild EnQueueQ,r.node-lchild, r.layer+1；ifr.node-rchild EnQueueQ,r.node-rchild, r.layer+1 /按层序入队时要随时标注结点所在层号 h=r.layer ； /最终一个队列元素所在层就是树的高度 formaxn=count0, i=1 ； h； i+ ifcountimaxn maxn=counti ； /求出哪一层结点数最多 return

17、h*maxn / Width 附加题：（ 15 分）7 / 9 名师归纳总结 - - - - - - -第 7 页,共 9 页精选学习资料 - - - - - - - - - 法二： 如不用帮助数组,不用层数重量也可以,关键在于如何区分层与层；有两种方法：一、通过比较指针判定是否到达新的一层的开头；二、通过比较指针判定是否到达当前层的末尾. 由于方法一对新的一层的开头点不易确定,比较次数要多于其次种,因此举荐其次种；对任意种类的树都适用,二叉树类似可得；算法如下：/- / TreeWidth 求树的宽度 / 不用帮助数组,不用层数重量 / 思路：/ 1.以两个整型变量存宽度,一个表示当前层的节

18、点数,一个表示当前已知最大宽度,当遍历完 一层后立刻判定两者大小,保留大者；/ 2.通过比较指针判定是否到达本层的末尾,以确定层与层间的关系；/- int TreeWidthTreeNode * T int iMaxCount=0,iRecCount=0 ；/iRecCount 当前层的节点数 ,iMaxCount 当前已知最大宽度 TreeNode * pP=T,* pLastChild=T ； /pP指向当前节点 ,pFirstChild 指向本层最末节点InitQueueQ； /队列初始化, Q 的元素为 TreeNode*类型 EnQueueQ,T； /根结点入队while.Queue

19、EmptyQ DeQueueQ,pP； /结点出队 iRecCount+；/出队时再把结点所在层的计数器加 1 ifhasChildpP EnQueueQ,pP-Child ；/有孩子就孩子入队 ifpP=pLastChild/ 如到达本层的末尾 / 先打算 iMaxCount , 再重置 iRecCount /求繁茂度不能清零此变量；iMaxCount=maxiMaxCount,iRecCount；iRecCount=0；QueueTailQ,pLastChild ； /读出队尾元素,留意不是出队 ./既已到本层末尾,又已将其孩子入队 return iMaxCount ；如有的话 , 就队尾

20、元素 必为下一层的最末元素 设 p、t 分别表示两棵没有度为1 的结点的二叉树；设计一种算法,找出p 和 t 中最大的同构子树并分析算法的时间复杂度（无需写出算法,描述思路即可）；注：“ 同构” 是指两个二叉树不仅结点数相同、并且它们的左右子树之间的关系也相同,但各结点的数据值可以不同；“ 最大的同构子树” 即结点最多的同构子树；解： 我们把一棵二叉树用树描述符来表示,就问题会变得简洁解决；所谓树描述符,即对每个结点按二叉树先序遍历并输出结点的度；例如左边二叉树的描述符为 202202200. 在此描述符8 / 9 名师归纳总结 - - - - - - -第 8 页,共 9 页精选学习资料 -

21、 - - - - - - - - 中,假如一个子串的字符数等于此子串中每个数字之和加1,就此子串肯定是一个子树；如上面的字符串中,2202200 是一个子树,由于他有7 个字符,每个字符数字和为2+2+2=6. 同理, 20220,200也是子树；问题转化为两个字符串中查找满意上述条件的最长公共子串；最长公共子串的算法已有（见习题）,只需在此算法中加上判定此子串是否是一个子树的条件即可；判定一个子串是否为一个子树的复杂度为 O（ n）,n 为字符串长度；由于求最长公共子串的复杂度为 Omn ,m、n 分别为 p 和 t 的结点数,判子串是否为子树的过程可以和求最长公共子串相结合,即在求最长公共子串中完成；就求最大同构子树的复杂度为 Omn ；9 / 9 名师归纳总结 - - - - - - -第 9 页,共 9 页