中央电大-&-数据结构---复习题----综合复习资料.doc(简答题).docx
《中央电大-&-数据结构---复习题----综合复习资料.doc(简答题).docx》由会员分享,可在线阅读,更多相关《中央电大-&-数据结构---复习题----综合复习资料.doc(简答题).docx(5页珍藏版)》请在咨信网上搜索。
1、电大数据结构复核习题(简答题)1、 简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现?答:若用结点表示某个数据元素,则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构.可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同,逻辑上相邻的结点,其物理地址未必相同,但可通过结点的内部信息,找到其相邻的结点,从而保留了逻辑结构的特点.采用的存储结构不同,对数据的操作在灵活性,算法复杂度等方面差别较大.2、 解释顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优
2、缺点。答:顺序结构存储时,相邻数据元素的存放地址也相邻,即逻辑结构和存储结构是统一的,,要求内存中存储单元的地址必须是连续的。优点:一般情况下,存储密度大,存储空间利用率高。缺点:(1)在做插入和删除操作时,需移动大量元素;(2)由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;(3)表的容量难以扩充。链式结构存储时,相邻数据元素可随意存放,所占空间分为两部分,一部分存放结点值,另一部分存放表示结点间关系的指针.优点:插入和删除元素时很方便,使用灵活。缺点:存储密度小,存储空间利用率低.3、 什么情况下用顺序表比链表好?答:顺序表适于做查找这样的静态操作,链表适于做插入和删
3、除这样的动态操作。如果线性表的变化长度变化不大,且其主要操作是查找,则采用顺序表;如果线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表.4、 解释头结点、第一个结点(或称首元结点)、头指针这三个概念的区别?答:头结点是在链表的开始结点之前附加的一个结点;第一个结点(或称首元结点)是链表中存储第一个数据元素的结点;头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。5、 解释带头结点的单链表和不带头结点的单链表的区别. 答:带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上,带头结点的单链表,不管链表是否为空,均含有一个头结点,不带头结点的
4、单链表不含头结点。在操作上,带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点,算法步骤都相同。不带头结点的单链表,其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点.因为两种情况的算法步骤不同.6、 与单链表相比,双向循环链表有哪些优点?答:双向循环链表设置了指向前驱和后继的指针,所用的地址空间增加,以空间复杂度代价换取时间复杂度的提高。双向循环链表可以从任一结点开始遍历整个链表。在动态内存管理中,应用双向循环链表可以从上次查找过的 结点开始继续查找可用结点,而单链表却每次都需要从表头开始查找。相比之下,双向循环链表的时间效率更高.7、 简述栈
5、和一般线性表的区别。答:栈是一种先进后出的线性表,栈的插入和删除操作都只能在栈顶进行,而一般的线性表可以在线性表的任何位置进行插入和删除操作.8、 简述队列和一般线性表的区别。答:队列是一种先进先出的线性表,队列的插入只能在队尾进行,队列的删除只能在队头进行,而一般的线性表可以在线性表的任何位置进行插入和删除操作.9、 链栈中为何不设头结点?答:因为链栈只在链头插入和删除结点,不可能在链表中间插入和删除结点,算法实现很简单,所以一般不设置头结点。10、 利用一个栈,则:(1)如果输入序列由A,B,C组成,试给出全部可能的输出序列和不可能的输出序列。(2)如果输入序列由A,B,C,D组成,试给出
6、全部可能的输出序列和不可能的输出序列.答:(1)栈的操作特点是后进先出,因此输出序列有:A入,A出,B入,B出,C入C出,输出序列为ABC.A入,A出,B入,C入,C出,B出,输出序列为ACB.A入,B入,B出,A出,C入,C出,输出序列为BAC。A入,B入,B出,C入,C出,A出,输出序列为BCA。A入,B入,C入,C出,B出,A出,输出序列为CBA。由A,B,C组成的数据项,除上述五个不同的组合外,还有一个C,A,B组合。但不可能先把C出栈,再把A出栈,(A不在栈顶位置),最后把B出栈,所以序列CAB不可能由输入序列A,B,C 通过栈得到。(2)按照上述方法,可能的输出序列有:ABCD,A
7、BDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA。不可能的输出序列有:DABC,ADBC,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABD11、 用S表示入栈操作,X表示出栈操作,若元素入栈顺序为1234,为了得到1342出栈顺序,相应的S和X操作串是什么?答:应是SXSSXSXX。各操作结果如下:S 1入栈X 1出栈 输出序列:1S 2入栈S 3入栈X 3出栈 输出序列:13S 4入栈 X 4出栈 输出序列:134X 2出栈 输出序列:1342 12、 有5个元素,其入栈次序为:A、B
8、、C、D、E,在各种可能的出栈次序中,以元素C、D最先的次序有哪几个?答:从题中可知,要使C第一个且D第二个出栈,应是A入栈,B入栈,C入栈,C出栈,D入栈.之后可以有以下几种情况:(1)B出栈,A出栈,E入栈,E出栈,输出序列为:CDBAE。(2)B出栈,E入栈,E出栈,A 出栈,输出序列为CDBEA。(3)E入栈,E出栈,B出栈,A出栈,输出序列为CDEBA所以可能的次序有:CDBAE,CDBEA,CDEBA13、 写出以下运算式的后缀算术运算式(1)3x2+x-1/x+5 (2)(A+B)CD/(E+F)+G答;对应的后缀算术运算式:(1)3x2x+1x/5+ (2)AB+CDEF+/-
9、G+14、 在什么情况下可以用递归解决问题?在写递归程序时应注意什么?答:该问题必须可以被分解为和该问题具有相同逻辑结构的子问题,即具有递归性质。书写递归程序的要点如下:(1)问题与自身的子问题具有类同的性质,被定义项在定义中的应用具有更小的尺度.(2)被定义项在最小尺度上有直接解。递归算法设计的原则是用自身的简单情况来定义自身,一步比一步简单,确定递归的控制条件非常重要,设计递归算法的方法是:(1)寻找方法,将问题化为原问题的子问题求解(例如n!=n(n-1)!).(2)设计递归出口,确定递归终止条件(例如求解n!时,当n=1时,n!=1).15、 简述广义表和线性表的区别和联系.答:广义表
10、是线性表的的推广,它也是n(n0)个元素a1 ,a2ai an的有限序列,其中ai或者是原子或者是一个广义表。所以,广义表是一种递归数据结构,而线性表没有这种特性,线性表可以看成广义表的特殊情况,当ai都是原子时,广义表退化成线性表。 16、 写出如下图所示的二叉树的先序、中序和后序遍历序列。答:二叉树的定义是递归的,所以,一棵二叉树可看作由根结点,左子树和右子树这三个基本部分组成,即依次遍历整个二叉树,又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分。.,这样划分一直进行到树叶结点。(1)先序为“根左右”,先序序列为:fdbacegihl(2)中序为“左根右”,中
11、序序列为:abcdefghij(3)后序为“左右根,后序序列为:acbedhjigf17、 已知某二叉树的先序遍历结果是:A,B,D,G,C,E,H,L,I,K,M,F和J,它的中序遍历结果是:G,D,B,A,L,H,E,K,I,M,C,F和J,请画出这棵二叉树,并写出该该二叉树后序遍历的结果。答:二叉树图形表示如下: 该二叉树后序遍历的结果是:G D B L H K M I E J F C A18、 已知一棵完全二叉树共有892个结点,求(1)树的高度(2)叶子结点数(3)单支结点数(4)最后一个非终端结点的序号答:(1)已知深度为k的二叉树最多有2k1个结点(K1), 29-1892 21
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中央电大 数据结构 复习题 综合 复习资料 doc 答题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。