数据结构复习之运算操作题(答案解析).pdf
《数据结构复习之运算操作题(答案解析).pdf》由会员分享,可在线阅读,更多相关《数据结构复习之运算操作题(答案解析).pdf(8页珍藏版)》请在咨信网上搜索。
1、 习题习题 4-1运算运算题题。1有 6 个元素 A、B、C、D、E、F 依次进栈,允许任何时候出栈,能否得到下列的每个出栈序列,若能,给出栈操作的过程,若不能,简述其理由。(1)CDBEFA (2)ABEDFC (3)DCEABF (4)BAEFCD 2有 4 个元素 a,b,c,d 依次进栈,任何时候都可以出栈,请写出所有可能的出栈序列和所有不存在的序列。3用一维数组 a7顺序储一个循环队列,队首和队尾指针分别用 front 和 rear 表示,当前队列中已有 5 个元素:23,45,67,80,34,其中,23 为队首元素,front 的值为 3,请画出对应的存储状态,当连续做 4 次出
2、队运算后,再让 15,36,48 元素依次进队,请再次画出对应的存储状态。4用于顺序存储一个队列的数组的长度为 N,队首和队尾指针分别为 front 和 rear,写出求此队列长度(即所含元素个数)的公式.参考答案(从简)1,(1)能:push(S,A),push(S,B),push(S,C),pop(S),push(S,D),pop(S),pop(S),push(S,E),pop(S),push(S,F),pop(S),pop(S).(2)能:push(S,A),pop(S),push(S,B),pop(S),push(S,C),push(S,D),push(S,E),pop(S),pop(
3、S),push(S,F),pop(S),pop(S).(3)不能:当 E 出栈时,AB 必需在栈内,而后继 A 出栈先于 B,不符合后进先出原则。(4)不能:当 F 出栈时,CD 必需在栈内,而后继 C 出栈先于 D,不符合后进先出原则。2,所有可能的出栈序列:abcd;abdc;acbd;acdb;adcb;bacd;badc;bcad;bcda;bdca;cbad;cbda;cdba;dcba.所有不存在的序列:adbc;bdac;cabd;cadb;cdab;dabc;dacb;dbac;dbca;dcab.3,0 1 2 3 4 5 6-80 34 23 45 67 rear fron
4、t 34 15 36 48 front rear4,队列长度 L 的计算公式为:L=(N+rear-front)%N 说明:当 rearfront 时,L=rear-front=(N+rear-front)%N;当 rearfront 时,队列被分为两个部分,前部分在数组的尾部,其元素个数为 N-1-front,后部分在数组的首部,其元素个数为 rear+1,所以:L=(rear+1+N-1-front)%N=(N+rear-front)%N;习题习题 6-1运算运算题题1.已知一组元素为(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉搜索树,再以广义表
5、的形式给出该二叉搜索树.2.已知一棵搜索树的广义表表示为 28(12(,16),49(34(30),72(63),若从中依次删除 72,12,49,28,等 4 个结点,试分别画出每删除一个结点后得到的图形表示的二叉搜索树,并写出对应的广义表表示.3.从空堆中开始依次向小根堆中插入集合38,64,52,15,73,40,48,55,26,12中的每个元素,试以顺序表的形式给出每插入一个元素后堆的状态.4.已知一个堆为12,15,40,38,26,52,48,64,若从堆中依次删除 4 个元素,请给出每删除一个元素后的堆的状态.5.有 7 个带权结点,其权值分别为 3,7,8,2,6,10,14
6、,试以它们为叶子结点构造一棵哈夫曼树,给出其广义表表示.并计算出带权路径长度 WPL.*6.在一份电文中共使用 5 种字符,即 a.b.c.d.e,它们的出现频率依次为 4,7,5,2,9,试画出对应的哈夫曼编码和传送电文的总长度.*7.一棵二叉树的广义表表示为 A(B(,D(G,),)C(E(,H),F),试画出对应的图示二叉树*9.一组关键字为(36,75,83,54,12,67,60,40,92,72),试依次插入结点分别生成一棵二叉搜索树,并求查找每个元素的平均查找长度.1.广义表:46(52(12,37(29),78(62(,70)3.3838 6438 64 5215 38 52
7、6415 38 52 64 7315 38 40 64 73 5215 38 40 64 73 52 4815 38 40 55 73 52 48 6415 26 40 38 73 52 48 64 5512 15 40 38 26 52 48 64 55 732.删除 72 删除 12 删除 49 删除 28 7.9.ASL=(1+22+23+34+25)/104.删除 1215 26 40 38 64 52 48删除 1526 38 40 48 64 52删除 2638 48 40 52 64删除 3840 48 64 525.广义表:(2,3),6),10),(7,8),14)WPL=(
8、10+14)2+(6+7+8)3+(2+3)46.字符编码码长a00004b012c0013d00014e11电文总长=44+72+53+24+91 习题习题 7-1运算运算题题1、如图 7-13(a)和图 7-13(b)所示,求:、1、每一个图的二元组表示。、2、图 7-13(a)中每个顶点的度,以及每个顶点的所有邻接点和所有边。、3、图 7-13(b)中每个顶点的入度、出度和度,以及每顶点的所有入边的出边。、4、图 7-13(a)中从 v0 到 v4 的所有简单路径及相应路径长度。、5、图 7-13(b)中从 v0 到 v4 的所有简单路径及相应带权路径长度。2、根据图 7-13(a)和图
9、 7-13(b),画出:、1、每个图的邻接邻接矩阵。、2、每个图的邻接表。、3、每个图的边集数组。3、如图 7-14 所示,按下列条件分别写出从顶点 v0 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。、1、假定它们均采用邻接矩阵表示。、2、假定它们均采用邻接表表示,并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。4、已知一个图的二元组表示如下:V=0,1,2,3,4,5,6,7,8E=(0,3),(0,4),(1,2),(1,4),(2,4),(2,5),(3,6),(3,7),(4,7),(5,8),(6,7),(7,8)、1、画出对应的图形。、2、
10、假定从顶点 0 出发,给出邻接矩阵表示图的深度优先和广度优先搜索遍历的顶点序列。、3、假定从顶点 0 出发,给出邻接表表示的图的深度优先和广度优先搜索遍历的顶点序列,假定每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。答案3.依照矩阵和邻接表所产生的两种遍历序列各自相等。a 图:深度优先遍历:0 1 2 8 3 4 5 6 7 9广度优先遍历:0 1 4 2 7 3 8 6 9 5b 图:深度优先遍历:0 1 4 5 8 7 2 3 6广度优先遍历:0 1 3 4 2 6 7 5 84.深度优先遍历:0 3 6 7 4 1 2 5 8广度优先遍历:0 3 4 6 7 1 2 8 5
11、(a)无向图 (b)有向图 图 713 运算题图 1 (a)无向图 (b)有向图 图 714 运算题图 2 习题习题 8-1运算运算题题1、如图形 8-18 所示,针对有向图操作如下。(1)画出最小生成树并求出它的权。(2)从顶点 v0 出发,要据普里姆算法求出最小生成树的过程中,把依次得到的各条边按序写出来。(3)根据克鲁斯卡算法求出最小生成树的过程中,把依次得到的各条边写出来。2、如图 8-19 所示,利用狄克特拉算法求从顶点 V0 到其余各顶点的最短路径,并画出对应的图形表示。3、已知一个图的二元组表示为:V=0,1,2,3,4,5,6,7 E=(0,1)8,(0,3)2,(0,5)10
12、,(1,2)6,(1,4)20,(1,6)12,(2,4)10,(2,7)15,(3,5)5,(3,6)7,(4,7)4,(5,6)6,(6,7)8(1)按照克鲁斯卡尔算法求出最小生成树,写出依次得到的各条边。(2)按照狄克斯特算法求从顶点 0 到其余各顶点的最短路径。(1)(0,3),(4,7),(3,5),(5,6),(1,2),(0,1),(6,7)(2)03:(0,3)05:(0,3),(3,5)01:(0,1)06:(0,3),(3,6)02:(0,1),(1,2)07:(0,3),(3,6),(6,7)04:(0,3),(3,6),(6,7),(7,4)4、如图形 8-20 所示,
13、利用弗洛伊德算法求每对顶点之间的最短路径,即仿照如图形 8-8 的运算过程,给出从邻接矩阵出发每加入一个中间每加入一个中间点后矩阵状态。5 如图形 8-21 所示,试给出一种拓扑序列,若在它的邻接表存储结构中,每个顶点邻接表中的边结点都是按照终点序号从大到小链接的,则按此给出唯一一种拓扑序列。6 一个 AOV 网的二元组表示为:V=0,1,2,3,4,5,6,7,8,9,10 E=,图 818 无向带权图 (1)(2)普里姆算法的边的序列:(0,1),(1,6),(6,2),(2,3),(3,4),(4,5)(3)克鲁斯卡算法的边的序列:(1,6),(2,3),(0,1),(6,2),(3,4
14、),(4,5)图 819 有向带权图不画图了,只写出边的序列。以下各点的最短路径是按顺序生成的:03:05:01:,06:,04:,02:,07:,图 820 有向带权图图 821 AOV 网 答案:1 4 0 2 3 5 7 6 8 9 在此 AOV 网的邻接表存储中,若各顶点邻接表中的边结点是按照邻接顶点序号从大到小链接的,请写出按此邻接表和介绍表和介绍的拓扑排序算法得到得到的拓扑排序算法得到的拓扑序列。提示:先画出图形再运算。答案:1 0 2 4 3 5 7 6 8 9 107、如图形 8-22 所示的 AOV 网,求:(1)每个事件的最早发生时间和最迟发生时间。(2)完成整个工程至少需
15、要多长时间。(3)每项活动的最早开始时间和最迟开始时间以及开始时间余量。(4)画出由所有关键活动所构成的图。(5)哪些活动加速可使整个工程提前完成?答案:(1)设 ve(i)和 vl(i)分别表示事件 i 的最早发生时间和最迟发生时间。ve(0)=0ve(1)=ve(0)+a1=5ve(2)=ve(0)+a2=6 ve(3)=Max ve(1)+a3,ve(2)+a4 =Max 8,12 =12 ve(4)=Max ve(2)+a5,ve(3)+a6 =Max 9,15 =15 ve(5)=ve(3)+a7=16 ve(6)=Max ve(3)+a8,ve(4)+a9 =Max 16,16 =
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 运算 操作 答案 解析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。