资源描述：
《数据结构期末考试复习总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《数据结构》期末考试题型及分值(1)简答題6题*5分=30分简要回答要点(2)分析题6题*5分=30分给出结果(3)设计题1题*10分=10分设计思想及结杲(4)编程题1题*10分=10分完整代码(5)综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析｛定义=功能(ADT)表示=存储结构体实现=算法(基本操作)算法分析=时间、空间复杂度｝考试概念有：1.数据结构｛一、线性表(栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构)二、非线性表(集合-树-图)｝2.抽象数据类型数据对象-数据关系-基本操作3.算法性质-要求(设计)-效率(度量)4.实
2、例查找：高效查找算法排序：高效的排序算法分析题考试题目参考(1)1-2-3-4-5-6顺序建BBST(2)6-5-4-3-2-1顺序建BBST数据结构复习资料一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。2.数据结构被形式地定义为（D，R），其屮D是数据元jfe的奋限集合，R是D上的关系存限集合。3.数据结构包括数据的逻辑结构、数据的存槠结构和数据的运算这H个方面的内界。4.数据结构按逻辑结构可分为两人类，它'｛门分别是线性结构和非线性结构95.线性结构屮元素之问存在一对一关系，树形结构屮元素之问存在一对多
3、关系，图形结构屮元素之阆存在多对多关系》6.在线性结构屮，第一个结点」2^_前驱结点，其余每个结点奋且只奋1个前驱结点:最后一个结点j査_后续结点，其余每个结点奋且只奋1个后续结点#7.在树形结构屮，树根结点没有前驱结点,其余毎个结点有且以有1个前驱结点:叶了结点没有后续结点，其余毎个结点的后续结点数可以任意多个。8.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。9.数据的存储结构可用四种基木的存储方法表示，它们分别是顺序、链式、索JI和敗列-10.数据的运算坡常用的旮5种，仑们分别是捅入、删除、修改、杏找、样序。11.一个灯法的效率可分为时间效率和宁间
4、效率。12.在顺序表屮插入或删除一个元素，需要平均移动表屮一半元素,具体移动的元素个数与表长和该元素在表屮的位置奋关。13.线性表中结点的集合是_奋限的,结点间的关系是_一对一的。14.一个长度为n的㈦景的第i个元紊＜1«11+1＞之前插入一个元紊时，需句后移动n-i+l个元紊。15.向一个长度为n的M景屮删除第i个元素时，需句前移动n-i个元素，简答题实例2.简述顺序表和链表存储方式的特点。头结点的作用卅1.空表勺非空表处理一忭2.结点之前操作更方便。答：顾序衣的优点足吋以随机w问数据元皮，缺/«:是人小固定.不利r•增减结点（增减结/入操作耑要移动元索）、链表的优
5、点足采用指针7/式增减结点.廿常//便（只需改变指针指向.不移动结点）。其缺点是布醮进行随机访问,只能顾序w问。另外，每个结点上增加指tr域，造出额外存储空叫增人。3.对a衣没托义结的作用足什么？（至少说出两条好处）答:其好处存:（1）Xj带失结点的链衣，沈衣的任何结点之前捕入结点或刪除表屮江何结所要做的都是修改前.-个銪点的指针域，因为任何元索结点都有前驱结点（荇链表没有头结点，则首元索结点没何前驱结点，在其前捕入结点和刪除该结点时操作a杂些）。（2）对带失结点的链表,表头格针是指向头结点的非空梅析，因表与非空表的处
6、一样的。设计题:(1)1.没计计算二叉树屮所釘结
7、点值之和的算法。voidsuni(bitiee*bt.mt&s){if(bt!=O){s=s+bt->data;siun(bt->lclnld,s);sum(bt->rchild.s):}没计在链式结构上实现简单选择排序算法。voidsimpleselectsorlklist(lklist*&liead){lklistmtmm.t;if(head==0
8、head->iiext==O)return:for(q=head:q!=O:q=q->iiext){mm=q->data:s=q;for(p=q->next:p!=O:p=p->iiext)if(mm>p->data)
9、{min=p->data:s=p;}if(s!=q){t=s->data:s->clata=q->data;q->data=t;}}}数据结构试卷（一〉三、计算题（每题6分，共24分）1.在如下数组A屮链接存储了一个线性表，表头指针为A[Ol.nexb试写出该线性表。Adatanext605078903440357204101234567线性表为：(78,50,40,60,34,90)L0110110011110011101101.请a山下图的邻接矩阵和邻接表。1.己知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2
