资源描述：
《《数据结构 》总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《《数据结构数据结构》》复习串讲复习串讲考试范围•本次考试涉及教材中全部章节的内容，包括–1.绪论2.线性表–3.稀疏矩阵和广义表4.栈和队列–5.树6.特殊二叉树–7.图8.图的应用–9.查找10.排序•其中第2章线性表和第5、6章树和二叉树为重点，第7、8章图和图的应用为次重点。其它章节也有涉及。考试题型•填空题(20%)•选择题(30%)•简答题(50%)如何复习•主要看参考教材，参考讲义。通过上机练习讲义中的实例巩固所学知识。•认真完成作业。•请认真复习下列复习重点中的各个知识点，着重复习标记双感叹号(!!)的知识点。•下面进入重点内容复习。第一章绪
2、论•1．数据结构的相关概念–数据，数据元素，数据项，关键字–数据结构，逻辑结构，存储结构，线性结构，非线性结构(!!)–抽象数据类型(!!)•2．算法及算法评价–算法5个特性(!!)-有穷、确定、可行、输入、输出–算法效率的衡量（时间复杂度）(!!)•重点提示：数据的逻辑结构（线性、集合、树、图），数据结构的二元组表示数据结构的形式定义描述为:数据结构是一个二元组B=(K,R)其中:K是数据元素的集合，R是K上二元关系的集合。•K上的一个关系r是序偶的集合。•对于r中的任一序偶(x,y K)，我们把x叫做序偶的第一元素，把y叫做序偶的第二元素•称序
3、偶的第一元素为第二元素的(直接)前驱，称序偶的第二元素为第一元素的(直接)后续，即在中x为y的前驱，y为x的后续•在图形表示中，每个结点对应一个数据元素，两结点之间带箭头的连线(有向边或弧)对应一个序偶，起始结点是第一元素，终止结点是第二元素从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构数据结构逻辑结构：线性结构（一对一）linearity(数据之间的树形结构（一对多）tree相互联系)图状或网状结构（多对多）graph集合结构（同属一个集合）set物理结构(存储结构)：(在计算机中的存储方式)顺序存储（利用在存
4、储器中相对位置之间的特定关系）链式存储（利用附加的“指针”）索引、散列等计算时间复杂度for(i=1;i<=n;i++)for(j=i;j<=n;j++)s++;例题•什么是数据结构?有关数据结构的讨论涉及哪三个方面?•数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上关系的有限集合。•计算机算法是指解决问题的有限运算序列，它必须具备输入，输出和可行性、确定性和有穷性等五个特性。•……第二章线性表（重点）•1．线性表的相关概念(!!)–线性表是最简单、最基本的一种线性数据结构，有两种存储表示方法（顺序和链接），三种主要基本操作（查找，插入
5、，删除）–线性表的定义，前驱，后继，线性表的长度，空表，线性表的抽象数据类型第二章线性表（重点）•2．顺序存储–顺序表的基本操作（查找，插入，删除）(!!)–顺序存储结构仅适用于不常进行插入删除的线性表(!!)第二章线性表（重点）•3．链接存储–单链表的存储表示，结点，数据域，指针域，指针，头指针，空指针(!!)–单链表的基本操作（求长度；查找；插入；删除）(!!)–循环链表和双向链表的特点、存储结构–顺序表和链表的比较：如何选用不同的存储结构，适用于何种操作(!!)例题•线性表可以采用哪两种存储结构？每种的优缺点是什么？什么时候该采用哪种结构？…•在一个长
6、度为n的顺序/链式存储线性表中，删除/添加第i个元素(1≤i≤n)后，需要依次前移多少个元素。(n-i/n-i+1)。表头、表尾插入呢？•查找元素的平均次数：n/2•……顺序表中删除/插入引起的移动123…ii+1…n123…ii+1…nn-i123…jii+1…nn-i+1第三章集合、稀疏矩阵和广义表•1.集合–集合的交、并、差(!!)•2．稀疏矩阵–稀疏矩阵的含义和存储结构（三元组顺序表和十字链表）•3．广义表基本概念–广义表的含义和存储结构（图形表示和链接存储）–广义表的求长度和求深度的运算(!!)求广义表的长度和深度•A=()•B=(e)•C=(a,
7、(b,c,d))•D=((),(e),(a,(b,c,d)))•E=((a,(a,b),((a,b),c)))•F=((a,(a,b),((a,b),c)),F)第四章栈和队列•栈–定义，结构特点（先进后出）(!!)–存储表示–操作：进栈，出栈，语法检查(!!)–后缀表达式的计算(!!)栈的例题•后缀表达式16943+*-所对应的计算结果为______________________。•在铁路调度栈进行车厢调度时，如果进站的车厢序列为123456，则能否得到324516的出站车厢序列_____；能否得到436512的出站车厢序列______。•向一个顺序栈插
8、入一个元素时，首先把待插入元素存储到这个位置上然后，
