电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

数据结构复习-铁宇彤完整版 v.0.1VIP免费

数据结构复习-铁宇彤完整版 v.0.1_第1页
1/14
数据结构复习-铁宇彤完整版 v.0.1_第2页
2/14
数据结构复习-铁宇彤完整版 v.0.1_第3页
3/14
考试题型选择题:21分填空题:18分判断题:15分图表题:26分算法题:20分1.什么是图的邻接矩阵表示法?什么是图的邻接表表示法?在这两种存储结构上如何计算顶点的度?邻接矩阵一个有n个顶点的图G=(V,E)的邻接矩阵是一个nn的矩阵A,A的每个元素是0或1。设V={0,1,2,……,n-1},如果G是无向图,则A的元素定义为:1(u,v)EA(u,v)=0其他如果G是有向图,则A的元素定义为:1EA(u,v)=0其他如果G是带权的图,则邻接矩阵中值为1的元素应替换为权值,有时需要将0替换为。(详见PPTunit7-120-21)邻接表要点:1.为图中每一个顶点建立一个单链表;2.顶点u的单链表中,每一个结点v表示一个邻接点,即代表一条边(u,v)或3.结点和边的结构如下:4.每个单链表的头指针存入一个一维数组,以表示一个图。(详见PPTunit7-120-21)2.什么是堆?什么是最大堆?什么是最小堆?如何利用下推(筛选)操作建堆?如何利用逐步插入结点(上推)的操作建堆?一个大小为n的堆(heap)是一棵包含n个结点的完全二叉树。每个结点的关键字值大于等于双亲结点的关键字值的堆称为最小堆(MinHeap)。最小堆的另一定义当完全二叉树以顺序方式存储时,实际上得到的是结点序列,所以最小堆又可以定义为:堆是n个元素的序列(k1,k2,…,kn),当且仅当满足kik2i且kik2i+1,(i=1,2,…,n/2)时,称为最小堆。函数AdjustDown(向下调整)设序列以顺序方式保存在一维数组中,数组元素具有可比较大小的类型。函数AdjustDown假定从数组中r+1到n,这n-r个位置上的元素已满足kik2i且kik2i+1,(i=r+1,2,…,n/2)条件,现向下调整第r位置上的元素,如果kr大于k2r和k2r+1,(即左、右孩子)中的较小的元素,则将kr与该较小元素交换,继续这样(向下调整)的过程,直到不再需要调整,或到达堆的底部为止。(详见PPTunit6堆排序PPTunit4-2堆)3.什么是二叉树的前序、中序、后序遍历?给出其中的两种遍历次序如何写出第三种遍历次序?先序遍历若二叉树为空,则空操作;否则,访问根结点;先序遍历左子树;先序遍历右子树。中序遍历若二叉树为空,则空操作;否则,中序遍历左子树;访问根结点;中序遍历右子树。后序遍历若二叉树为空,则空操作;否则,后序遍历左子树;后序遍历右子树;访问根结点。(详见PPTunit4-121-22)4.什么是二叉搜索树和AVL树?有何性质?如何进行插入和查找的操作?二叉搜索树(binarysearchtree)也称二叉排序树(binarysorttree)。二叉搜索树或者是一棵空二叉树,或者是具有下列性质的二叉树:(1)每个结点由关键字值表征,所有结点的关键字值各不相同;(2)若左子树不空,则左子树上所有结点的关键字值均小于根结点的关键字值;(3)若右子树不空,则右子树上所有结点的关键字值均大于根结点的关键字值;(4)左、右子树也分别是二叉搜索树。(详见PPTunit5-122)二叉搜索树的搜索算法搜索算法思路是:若二叉树为空,则搜索失败。否则,将k与根的关键字值比较,若k小于该关键字值,则用同样的方法搜索左子树,而不必搜索右子树;若k大于该关键字值,则用同样的方法搜索右子树,而不必搜索左子树;若k等于该关键字值,则搜索成功终止。二叉搜索树的插入算法插入算法思路是:(1)确定新元素的插入位置。搜索插入位置的方法与Search函数的做法类似,但要求在从根结点往下搜索过程中,用指针q记录下当前元素的双亲结点。如果在搜索中,遇到相同关键字值的元素,则表明有重复元素,那么显示Duplicate信息。(2)插入新元素如果二叉搜索树是空树,则新元素e成为树根。如果e的关键字值小于q结点的值,则将新元素e作为q的左孩子,否则作为其右孩子。AVL树:一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:它的左子树和右子树都是AVL树,且左子树和右子树的高度之差的绝对值不超过1。(每个结点附加一个数字,给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance。)(详见PPTunit5-24)AVL树的插入(详见PPTunit5-2)在向一棵本来是高度平衡的AVL树中插入一个新结点时,如果树中某个结点的平衡因子的绝对值|balance|>1,则出现了不平衡,需要做平衡化处理。在AVL树...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

数据结构复习-铁宇彤完整版 v.0.1

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部