数据结构考前辅导.ppt

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