数据结构(C语言).doc
《数据结构(C语言).doc》由会员分享,可在线阅读,更多相关《数据结构(C语言).doc(11页珍藏版)》请在咨信网上搜索。
《数据结构与算法》复习题 应用简答题。 1.有下列几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表示,并指出它们分别属于何种结构。 (1)A = {D,R},其中:D={a,b,c,d,e,f,g,h},R ={r}, r = {<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>} (2)B = {D,R},其中:D={a,b,c,d,e,f,g,h},R ={r}, r = {<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>} (3)C = {D,R},其中:D={1,2,3,4,5,6},R ={r}, r = {(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 2.简述顺序表和链表存储方式的特点。 答:顺序表的优点是可以随机访问数据元素,缺点是大小固定,不利于增减结点(增减结点操作需要移动元素)。链表的优点是采用指针方式增减结点,非常方便(只需改变指针指向,不移动结点)。其缺点是不能进行随机访问,只能顺序访问。另外,每个结点上增加指针域,造出额外存储空间增大。 3.对链表设置头结点的作用是什么?(至少说出两条好处) 答:其好处有: (1)对带头结点的链表,在表的任何结点之前插入结点或删除表中任何结点,所要做的都是修改前一个结点的指针域,因为任何元素结点都有前驱结点(若链表没有头结点,则首元素结点没有前驱结点,在其前插入结点和删除该结点时操作复杂些)。 (2)对带头结点的链表,表头指针是指向头结点的非空指针,因此空表与非空表的处理是一样的。 4.对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C组成,试给出全部可能的输出序列。 5.设有4个元素1、2、3、4依次进栈,而栈的操作可随时进行(进出栈可任意交错进行,但要保证进栈次序不破坏1、2、3、4的相对次序),请写出所有不可能的出栈次序和所有可能的出栈次序。 6.现有稀疏矩阵A如图所示,要求画出三元组表示法和十字链表表示法: 7.设4维数组的4个下标的范围分别为 [-1,0],[1,2],[1,3],[-2,-1],请分别按行序和列序列出各元素。 8.有一份电文中共使用5个字符:a,b,c,d,e,它们出现的频率依次为4,7,5,2,9,试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造),并求出每个字符的哈夫曼编码。 9.有如图所示的二叉树,回答如下问题。 (1) 写出该树的中序遍历序列; (2) 写出该树的先序遍历序列; (3) 写出该树的后序遍历序列; (4) 画出该二叉树的中序线索二叉树; (5) 画出该二叉树的后序线索二叉树; (6) 画出该二叉树对应的森林; 10.已知一棵树边的集合为{<i,m>,<i,n>,<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h> ,<a,c>},画出这棵树。 11.假设二叉树采用顺序存储结构,如图所示。 (1) 画出二叉树表示; (2) 写出先序遍历、中序遍历和后序遍历的结果; (3) 写出结点值c的双亲结点,其左、右孩子; (4) 画出把此二叉树还原成森林的图。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b 12.已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树。 13.某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,给出其后序遍历序列。 14.将下图所示森林转换成为二叉树,并写出转化后二叉树中序遍历结果。 15.有一份电文中共使用8个字符:a、b、c、d、e、f、o、i,它们的出现频率依次为10,20,15,32,40,60,26,18。试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造),并求出每个字符的哈夫曼编码。 16.已知某系统在通信联络中只可能出现A,B,C,D,E,F,G,H八种字符,其频率为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11试设计哈夫曼编码。 17.对有五个顶点{v1,v2,v3,v4,v5}的图的邻接矩阵如图所示,解答下列问题: (1)画出逻辑图。 (2)画出该逻辑结构的邻接表。 (3)基于邻接矩阵写出图的深度、广度优先遍历序列。 18.如图所示,解答如下问题: (1)写出从定点A出发,深度和广度优先遍历方法遍历该图的顶点序列。 (2)根据普里姆算法和克鲁斯卡尔算法,分别求它的最小生成树,要求给出构造过程。 19.给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上,指出从顶点1出发的深度优先遍历和广度优先遍历序列。 20.使用普里姆算法构造出如图所示的图G的一棵最小生成树。 21.使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。 22.设有一棵二叉树,它的中序和后序遍历结果如下,请画出该二叉树。 中序:1 4 3 5 6 2 后序:4 6 5 3 2 1 23.设一棵顺序二叉树具有10个结点,请计算其中叶子结点的数目。 24.设如图所示二叉树是由某棵树转化而来,请画出其对应的原树。 25.设有如图所示的一棵树,请将其转化为二叉树。 26.下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问题: (1)画出相应的AOE图; (2)给出各事件的最早发生时间和最晚发生时间; (3)找出关键路径,并指明完成该工程所需最短时间; (4)若把AOE网视为AOV网,给出其一个拓扑序列的例子。 工序代号 A B C D E F G H I J K L M M 时间 15 10 50 8 15 40 90 15 80 60 15 30 20 40 先驱工作 - - A,B B C,D B E G,I E I F,I H,J,K L G 27.某不带权有向图如下所示。给出其邻接矩阵和邻接表表示。 28.求如下AOE图的关键路径,要求给出求解过程。 29.有一组数据,内容如下:8,15,38,57,68,88,98,108,129,234,256 试用二分查找法查找68和222,要求先画出二叉折半检索树,然后写出查找过程。 30.已知有序表为{12,18,24,35,47,50,62,83,90,115,134},请画出采用折半查找法对应的判断树。 31.设数据集合d={1,12,5,8,3,10,7,13,9},试完成下列各题: (1)依次取d中各数据,构造一棵二叉排序树bt。 (2)如何依据此二叉树bt得到d的一个有序序列。 (3)画出在二叉树bt中删除“12”后的树结构。 32.对给定的数列R={7,16,4,8,20,9,6,18,5},构造一棵二叉排序树,并且 (1)给出按中序遍历得到的数列R1。 (1)给出按后序遍历得到的数列R2。 33.已知序列{17,18,60,40,7,32,73,65,85},请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。 34.已知序列{503,87,512,61,908,170,897,275,653,462},请给出采用快速排序法对该序列作升序排序时每一趟的结果。 35.已知序列{503,87,512,61,908,170,897,275,653,462},请给出采用堆排序法对该序列作升序排序时每一趟的结果。 36.已知序列{503,87,512,61,908,170,897,275,653,462},请给出采用希尔排序法对该序列作升序排序时每一趟的结果。 37.已知序列{17,18,60,40,7,32,73,65,85},请给出采用直接插入排序法对该序列作升序排序时每一趟的结果。 38.设散列表的长度m=13(0,1,2,…,12),散列函数为H(k)=k mod m,给定的关键字序列为{19,14,23,10,68,20,84,27,55,11}。试画出用线性探测法解决冲突时所构造的散列表。- 配套讲稿:
如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。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文