《数据结构考前辅导》由会员分享，可在线阅读，更多相关《数据结构考前辅导（59页珍藏版）》请在金锄头文库上搜索。
1、数据结构考前辅导主讲人:袁晓娟重点章节l第第3章章栈和队列栈和队列l第第6章章树和二叉树树和二叉树l第第7章章图图l第第9章章查找查找第1章 绪论1.数据结构定义数据结构定义:数据结构是一门研究非数值的程序设计数据结构是一门研究非数值的程序设计问题中计算机的操作对象以及它们之间问题中计算机的操作对象以及它们之间的关系和操作等的学科。的关系和操作等的学科。2.数据元素是数据的基本单位数据元素是数据的基本单位,数据项是数据的不可分割的最小单位数据项是数据的不可分割的最小单位.3.数据结构是带有结构数据结构是带有结构(相互之间存在一种相互之间存在一种或多种特定关系或多种特定关系)的数据元素的集合的数
2、据元素的集合.4.数据结构的四类基本结构数据结构的四类基本结构:(1)集合集合(2)线性结构线性结构(3)树形结构树形结构(4)图形结构或网状结构图形结构或网状结构线性结构与非线性结构的不同点线性结构与非线性结构的不同点:线性结构反映结点间的逻辑关系是一对一线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多的，非线性结构反映结点间的逻辑关系是多对多的。对多的。第2章 线性表1.线性表线性表:n个数据元素的有限序列个数据元素的有限序列.线性表是有限序列线性表是有限序列,可以为空可以为空.2.单链表单链表(线性链表线性链表)单链表单链表(线性链表线性链表)的结点包括两个域的
3、结点包括两个域:数据域数据域:存储数据元素信息的域存储数据元素信息的域.指针域指针域:存储直接后继存储位置的域存储直接后继存储位置的域.例例1:下面关于线性表的叙述中，错误的是哪一个？下面关于线性表的叙述中，错误的是哪一个？（B）A线性表采用顺序存储，必须占用一片连续的存线性表采用顺序存储，必须占用一片连续的存储单元。储单元。B线性表采用顺序存储，便于进行插入和删除操线性表采用顺序存储，便于进行插入和删除操作。作。C线性表采用链接存储，不必占用一片连续的存线性表采用链接存储，不必占用一片连续的存储单元。储单元。D线性表采用链接存储，便于插入和删除操作。线性表采用链接存储，便于插入和删除操作。第
4、3章 栈和队列1.栈栈:限定仅在表尾进行插入或删除操作的限定仅在表尾进行插入或删除操作的线线性表。性表。2.栈栈:后进先出后进先出.例例1:一个栈的入栈序列一个栈的入栈序列是是A、B、C、E、D，五个，五个元素都入栈后，首次出栈元素都入栈后，首次出栈的元素是的元素是_。(D)A.AB.EC.BD.DDECBA3.队列队列:是一种先进先出的线性表，它只允是一种先进先出的线性表，它只允许在表的一端进行插入许在表的一端进行插入(队尾队尾)，而在另一，而在另一端删除元素端删除元素(队头队头)。注注:栈和队列都是操作受限的线性表栈和队列都是操作受限的线性表.例例2:一个队列的入队序列是一个队列的入队序列
5、是1、3、4、2，则队列的首次输出元素是则队列的首次输出元素是_。(C)A、3B、2C、1D、41头3424.链式队列链式队列(链队列链队列):用链表表示的队列用链表表示的队列.5.链式队列为空的判定条件链式队列为空的判定条件:Q.front=Q.rear6.顺序队列顺序队列顺序队列的顺序队列的“假溢出假溢出”是怎样产生的是怎样产生的?一般的一维数组队列的尾指针已经到了数一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫组中还有空位置，这就叫“假溢出假溢出”。第四章 串1.串串(字符串字符串):由零个或多个字符组成
6、的有限序列由零个或多个字符组成的有限序列.2.空空串串:零个字符组成的串零个字符组成的串.空格串空格串:由一个或多个空格组成的串由一个或多个空格组成的串.3.串的长度串的长度:串中元素的个数串中元素的个数.例例1:设设s=“IAMAWOMAN”,则字符串的长度则字符串的长度为为_.(B)A、11B、12C、14D、154.串联接串联接Concat(&T,s1,s2)假设假设s1,s2,T都是都是ssting型的串变量型的串变量,且串且串T是由是由s1联结联结s2得到的得到的,即即:T的值的前一段和的值的前一段和s1的值相等的值相等,T的值的后一段和的值的后一段和s2的值相等的值相等.例例2:设
7、设s1=“GOOD”,s2=“BYE!”则字符串则字符串s1和和s2连接后的结果是连接后的结果是_。(D)A、BYEGOOD!B、GOODBYE!C、BYEDGOOD!D、GOODBYE!第五章 数组和广义表1.广义表一般记为广义表一般记为:LS=(a1,a2,an)当广义表当广义表LS非空时非空时,称第一个元素称第一个元素a1为为LS的表头的表头,其余元素组成的其余元素组成的表表(a2,a3,an)是是LS的表尾的表尾.一个广义表的表尾总是一个广义表 例例1:（判断）（判断）一个广义表的表头总是一个广义表一个广义表的表头总是一个广义表(F)例例2:广义表（广义表（ab）,ab）的表尾是）的表
8、尾是_(C)A、abB、abC、（、（ab）D、(ab)思考：思考：1）表头是什么？）表头是什么？（ab）2）广义表（）广义表（a）,ab）的表头，表尾分别是？）的表头，表尾分别是？（a）（ab）第6章 树和二叉树1.二叉树二叉树:每个结点至多只有二棵子树每个结点至多只有二棵子树,并且并且,二二叉树的子树有左右之分叉树的子树有左右之分,其次序不能任意颠其次序不能任意颠倒倒.例例1:三个结点的二叉树可以有哪几种形式？三个结点的二叉树可以有哪几种形式？例例2:一棵度为一棵度为2的树与一棵二叉树有何区别？的树与一棵二叉树有何区别？度为度为2的树从形式上看与二叉树很相似，的树从形式上看与二叉树很相似，
9、但它的子树是无序的，而二叉树是有序的。即，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子分其左右次序，而在二叉树中即使是一个孩子也有左右之分。也有左右之分。2.在二叉树的第在二叉树的第i层上至多有层上至多有2(i-1)个结点个结点(i=1).3.深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(i=1).4.满二叉树满二叉树:一棵深度为一棵深度为k且有且有2k-1个结点的二个结点的二叉树叉树.5.完全二叉树完全二叉树:深度为深度为k,有有n个结点的二叉树个结点的二叉
10、树,当且仅当其每一个结点都与深度为当且仅当其每一个结点都与深度为k的满二的满二叉树中编号从叉树中编号从1至至n的结点一一对应的结点一一对应.例例3:对完全二叉树叙述正确的是对完全二叉树叙述正确的是（B）A、完全二叉树就是满二叉树、完全二叉树就是满二叉树B、完全二叉树同一层上左子树未满不会有右、完全二叉树同一层上左子树未满不会有右子树子树C、完全二叉树和满二叉树编号不对应、完全二叉树和满二叉树编号不对应D、以上都不正确、以上都不正确6.遍历二叉树的操作定义遍历二叉树的操作定义先序遍历二叉树的操作定义为先序遍历二叉树的操作定义为:若二叉树为空若二叉树为空,则空操作则空操作;否则否则(1)访问根结点
11、访问根结点;(2)先序遍历左子树先序遍历左子树;(3)先序遍历右子树先序遍历右子树.中序遍历二叉树的操作定义为中序遍历二叉树的操作定义为:若二叉树为空若二叉树为空,则空操作则空操作;否则否则(1)中序遍历左子树中序遍历左子树;(2)访问根结点访问根结点;(3)中序遍历右子树中序遍历右子树.后序遍历二叉树的操作定义为后序遍历二叉树的操作定义为:若二叉树为空若二叉树为空,则空操作则空操作;否则否则(1)后序遍历左子树后序遍历左子树;(2)后序遍历右子树后序遍历右子树.(3)访问根结点访问根结点;例例4:如图所示二叉树，分别写出先序，中序，如图所示二叉树，分别写出先序，中序，后序遍历结果后序遍历结果
12、先序序列：- + a * b c d / e f中序序列: a + b * c d e / f后序序列：a b c d - * + e f / -例例5:已知一棵二叉树已知一棵二叉树中序和后序序列为分中序和后序序列为分别为别为:BDCEAFHG和和DECBHGFA 画出这棵二叉树。画出这棵二叉树。7.哈夫曼树构造方法哈夫曼树构造方法:1.根据给定的根据给定的n个权值个权值w1,w2,wn构成构成n棵二棵二叉叉树的集合树的集合F=T1,T2,.,Tn，其中每棵二叉树，其中每棵二叉树Ti中中只有一个带权只有一个带权wi的根结点，左右子树均空。的根结点，左右子树均空。2.在在F中选择两棵根结点权值最
13、小的树作为左右子中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。点的权值为其左右子树上根结点的权值之和。3.在在F中删除这两棵树，并将新的二叉树加入中删除这两棵树，并将新的二叉树加入F中。中。4.重复前两步（重复前两步（2和和3），直到），直到F中只含有一棵树为中只含有一棵树为止。该树即为哈夫曼树止。该树即为哈夫曼树例例6:已知给定权的集合已知给定权的集合5、29、8、7、14、23、11、3，构造相应的哈夫曼树。，构造相应的哈夫曼树。 8 29 15 14 23 11 8 29
14、8 7 14 23 11 5 29 8 7 14 23 11 3 42 58 42 29 29 19 29 29 23 19 29 15 14 23100第七章 图1.图分为图分为:有向图和无向图有向图和无向图.2.顶点顶点v的入度的入度:以顶点以顶点v为头的弧的数目为头的弧的数目.顶点顶点v的出度的出度:以顶点以顶点v为尾的弧的数目为尾的弧的数目.3.一个连通图的生成树一个连通图的生成树:是一个极小连通子图是一个极小连通子图,它含有图中全部顶点它含有图中全部顶点,但只但只有足以构成一棵树的有足以构成一棵树的n-1条边条边.4.图的表示法图的表示法:邻接表邻接表,邻接多重表邻接多重表,十字链表
15、十字链表5.数组表示法数组表示法(邻接矩阵邻接矩阵):以二维数组表示有以二维数组表示有n个顶个顶点的图时点的图时,需存放需存放n个顶点信息和个顶点信息和n2个弧信息的个弧信息的存储量存储量.6.图的邻接矩阵表示法适用于表示图的邻接矩阵表示法适用于表示(稠密图稠密图).7.邻接表：是图的一种链式邻接表：是图的一种链式存储存储结构。在邻接表中，结构。在邻接表中，对图中每个顶点建立一个单链表，第对图中每个顶点建立一个单链表，第i个单链表中个单链表中的结点表示依附于顶点的结点表示依附于顶点vi的边（对有向图是以顶的边（对有向图是以顶点点vi为尾的弧）。为尾的弧）。邻接表由两部分构成：表头结头、表结点组
16、成的邻接表由两部分构成：表头结头、表结点组成的单链表。单链表。邻接表的表示意义为：对于图邻接表的表示意义为：对于图G=(V,E)，若，若(i,j)E，则第，则第i个表头结点的单链表上有一个邻接点个表头结点的单链表上有一个邻接点域为域为j的表结头。的表结头。8.逆邻接表逆邻接表(专科生不要求专科生不要求)在有向图中，对在有向图中，对每个顶点每个顶点vi建立一个链接以建立一个链接以vi为头的弧表。为头的弧表。逆邻接表在形式上由两部分构成：表逆邻接表在形式上由两部分构成：表头结点、表结点组成的单链表。表头结点头结点、表结点组成的单链表。表头结点与邻接表完全一样，但表结点组成的单链与邻接表完全一样，但
17、表结点组成的单链表是不同的。表是不同的。逆邻接表的表示意义为：对于图逆邻接表的表示意义为：对于图G=(V,E)，若，若i,jE，则第，则第j个表头结点个表头结点的单链表上有一个邻接点域为的单链表上有一个邻接点域为i的表结头。的表结头。例例1:表头结头表头结头例例2:已知如图所示的已知如图所示的有向图，请给出该图有向图，请给出该图的的:（1）每个顶点的入）每个顶点的入/出出度；度；（2）邻接矩阵；）邻接矩阵；（3）邻接表；）邻接表；（4）逆邻接表。）逆邻接表。顶点点1 12 23 34 45 56 6入入度度出出度度9.图的遍历图的遍历:从图中某一顶点出发访遍图中其从图中某一顶点出发访遍图中其余
18、顶点余顶点,且使每一个顶点仅被访问一次且使每一个顶点仅被访问一次.10.两条遍历图的途径两条遍历图的途径:深度优先搜索深度优先搜索,广度优先搜索广度优先搜索.11.图的广度优先遍历算法类似于二叉树的图的广度优先遍历算法类似于二叉树的(层次遍历层次遍历).12.普里姆算法描述：普里姆算法描述：假设假设N(V，E)是一个连通图，是一个连通图，TE是是N上最小生上最小生成树中边的集合。算法从成树中边的集合。算法从Uu0(u0V)，TE开始，开始，重复执行下述操作：重复执行下述操作：在所有在所有uU，vV-U的边的边(u，v)E中找一条权中找一条权值最小的边值最小的边(u，v)并入集合并入集合TE，同
19、时，同时v并入并入U，直，直至至UV为止。此时为止。此时TE中必有中必有n-1边，则边，则T(V，TE)为为N的最小生成树。的最小生成树。13.克鲁斯卡尔算法克鲁斯卡尔算法假设假设WN=(V,E)是一个含有是一个含有n个顶点的连通个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含程为：先构造一个只含n个顶点，而边集为空的个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有根结点，则它是一个含有n棵树的一个森林。之棵树的一个森林。之后，从网的边集后，从网的边
20、集E中选取一条权值最小的边，若中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有树，也即子图中含有n-1条边为止。条边为止。例例3:已知无向图各边权值：已知无向图各边权值：（v1，v2）
21、=6；（v1，v3）=1；（；（v1，v4）=5；（v2，v3）=5；（；（v2，v5）=3；（；（v3，v4）=5；（v3，v5）=6；（；（v3，v6）=4；（；（v4，v6）=2；（v5，v6）=6；请用普利姆算法构造最小生请用普利姆算法构造最小生成树（限本科生做）成树（限本科生做）14V1V3V4V2V5V653555626v1 v2 v3 v4 v5 v6 15451V1V3V4V2V5V655556 v2 V1 v4V3 v5 v641V1V3V4V2V5V6左边的答题时可以不写左边的答题时可以不写v5v1v3v6v4v25665552V141V1V3V4V2V5V6255V6V3
22、V4V5V266541V1V3V4V2V5V62V5V1V336V2V4V663541V1V3V4V2V5V62例例4:已知无向图各边权值：（已知无向图各边权值：（1，2）=6；（；（1，3）=1；（；（1，4）=5；（；（2，3）=5；（；（2，5）=3；（；（3，4）=5；（；（3，5）=6；（；（3，6）=4；（；（4，6）=2；（；（5，6）=6；求求最小生成树，方法不限。最小生成树，方法不限。141342565356562641 2 3 4 5 6 156113425655656 2 1 43 5 6411342565 1 3 6426665552 141134256256 6 3
23、4526654113425625 1 336 2 4 663541 1 3 4 2 5 62例例5:普里姆算法、克鲁斯卡尔算法求最小生普里姆算法、克鲁斯卡尔算法求最小生成树成树.普里姆算法求最小生成树:41 2 3 4 5 6 12558526 2 1 43 5 66 1 3 45256468 185 6 3 452665 1 336 2 4 66克鲁斯卡尔算法求最小生成树:第9章 查找1.查找表：是由同一类型的数据元素（或记查找表：是由同一类型的数据元素（或记录）构录）构成的集合。成的集合。2.折半查找算法思想：折半查找算法思想：将数列按有序化将数列按有序化(递增或递减递增或递减)排列，查找
24、过程中排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。部分。通过一次比较，将查找区间缩小一半。例例1:折半查找适用于：折半查找适用于：_.(B)A、采用链式存储结构的有序表、采用链式存储结构的有序表B、采用顺序存储结构的有序表、采用顺序存储结构的有序表C、采用链式存储结构的无序表、采用链式存储结构的无序表D、采用顺序存储结构的无序表、采用
25、顺序存储结构的无序表3.折半查找过程的判定树折半查找过程的判定树:树中每个结点表示表中一个记录树中每个结点表示表中一个记录,结点中的结点中的值为该记录在表中的位置值为该记录在表中的位置.结点所在的层次结点所在的层次为第几次查找到为第几次查找到.例例2:假定对有序表：（假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半）进行折半查找，试回答下列问题：查找，试回答下列问题：a.画出描述折半查找过程的判定树；画出描述折半查找过程的判定树；b.若查找元素若查找元素54，需依次与哪些元素比较？，需依次与哪些元素比较？c.若查找元素若查找元素90，需依次与哪些元素比较
26、？，需依次与哪些元素比较？3 3，4 4，5 5，7 7，2424，3030，4242，5454，6363，7272，8787，9595(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；(3) 查找元素90，需依次与30, 63,87, 95等元素比较；4.二叉树是指结点的度最大为二叉树是指结点的度最大为2，也就是一个，也就是一个结点最多只有两个分支。二叉树与度为结点最多只有两个分支。二叉树与度为2的的树的区别是二叉树是顺序树，即有严格的树的区别是二叉树是顺序树，即有严格的左右之分，而度为左右之分，而度为2的树却没有这种要求。的树却没有这种要求。二叉排序树二叉排序树(二叉
27、查找树二叉查找树)是在二叉树的基是在二叉树的基础上面将小于结点的分支都放在该结点的础上面将小于结点的分支都放在该结点的左边，而大于该结点的分支都放在右边的左边，而大于该结点的分支都放在右边的树，这样很便于查找。树，这样很便于查找。例例3:在一棵空的二叉查找树中依次插入关键在一棵空的二叉查找树中依次插入关键字序列为字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。，请画出所得到的二叉查找树。12717212111649135.平衡二叉树的平衡因子只可能是平衡二叉树的平衡因子只可能是-1、0、1.6.哈希表不需要进行比较便可以直接取得所查记录哈希表不需要进行比较
28、便可以直接取得所查记录.7.哈希表构造方法哈希表构造方法:直接定址法直接定址法,数字分析法数字分析法,平方取平方取中法中法,折叠法折叠法,除留余数法除留余数法,随机数法随机数法.8.处理冲突的方法处理冲突的方法:什么是冲突什么是冲突?处理冲突的方法是什么处理冲突的方法是什么?若某个散列函数若某个散列函数H对于不相等的关键字对于不相等的关键字key1和和key2得到相同的散列地址得到相同的散列地址(即即H(key1)=H(key2)则将该现象称为冲突则将该现象称为冲突.解决冲突的方法有解决冲突的方法有:开放定址法和链地址法开放定址法和链地址法.例例3:设哈希表长设哈希表长m=18，哈希函数，哈希
29、函数H（key）=key%13；表中已有；表中已有3个结点个结点H（19）=6H(27)=1H(23)=10其余地址为其余地址为空，如用线性探测再散列处理冲突，关键空，如用线性探测再散列处理冲突，关键字字14的地址是的地址是_。(B)A、1B、2C、3D、以上都不正确、以上都不正确Hi=(H(key)+di)modmi=1第10章 排序其它排序方法了解其它排序方法了解.我只讲希尔排序我只讲希尔排序1.希尔排序基本思想希尔排序基本思想先取一个小于先取一个小于n的整数的整数d1作为第一个增量，把作为第一个增量，把文件的全部记录分成文件的全部记录分成d1个组。所有距离为个组。所有距离为dl的的倍数的
30、记录放在同一个组中。先在各组内进行倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量直接插入排序；然后，取第二个增量d2d1重重复上述的分组和排序，直至所取的增量复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同，即所有记录放在同一组中进行直接插入排序为止。一组中进行直接插入排序为止。例例:已知序列：已知序列：4938659776132748554选出步长为选出步长为5进行希尔排序，所得结果为进行希尔排序，所得结果为（A）A、1327485544938659776B、1344838274955659776C、4132738484955657697D、4913274876386597554考试题型介绍l1、单项选择题（、单项选择题（20分）分）l2、判断题判断题（10分）分）l3、名词解释名词解释（10分）分）l4、简答题、简答题（20分）分）l5、计算题计算题（40分）分）考试准备和注意事项考试准备和注意事项1、认真学习和掌握今天辅导的内容。2、网上的4套练习题必须要看的。3、看咱们网上的精华1帖子。祝：同学们都取得好成绩！ 谢谢大家！ 再见！
