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

考试题型 选择题： 21分填空题： 18分判断题： 15分图表题： 26分算法题： 20分 1.什么是图的邻接矩阵表示法？什么是图的邻接表表示法？在这两种存储结构上如何计算顶点的度？邻接矩阵一个有n个顶点的图G=(V,E)的邻接矩阵是一个nn的矩阵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替换为 。(详见PPT unit7-1 20-21)邻接表要点： 1. 为图中每一个顶点建立一个单链表； 2. 顶点u的单链表中，每一个结点v表示一个邻接点， 即代表一条边(u,v) 或 3. 结点和边的结构如下：4.每个单链表的头指针存入一个一维数组，以表示一个图。(详见PPT unit7-1 20-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与该较小元素交换，继续这样(向下调整)的过程，直到不再需要调整，或到达堆的底部为止。（详见PPT unit 6 堆排序 PPT unit 4-2 堆）3.什么是二叉树的前序、中序、后序遍历？给出其中的两种遍历次序如何写出第三种遍历次序？先序遍历若二叉树为空，则空操作；否则,访问根结点；先序遍历左子树；先序遍历右子树。中序遍历若二叉树为空，则空操作；否则,中序遍历左子树；访问根结点；中序遍历右子树。后序遍历 若二叉树为空，则空操作；否则,后序遍历左子树；后序遍历右子树；访问根结点。(详见PPT unit4-1 21-22)4.什么是二叉搜索树和AVL树？有何性质？如何进行插入和查找的操作？二叉搜索树（binary search tree）也称二叉排序树（binary sort tree）。二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：（1）每个结点由关键字值表征，所有结点的关键字值各不相同；（2）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（3）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；（4）左、右子树也分别是二叉搜索树。(详见PPT unit5-1 22)二叉搜索树的搜索算法 搜索算法思路是：若二叉树为空，则搜索失败。否则，将k与根的关键字值比较，若k小于该关键字值，则用同样的方法搜索左子树，而不必搜索右子树;若k大于该关键字值，则用同样的方法搜索右子树，而不必搜索左子树;若k等于该关键字值，则搜索成功终止。二叉搜索树的插入算法 插入算法思路是： (1)确定新元素的插入位置。 搜索插入位置的方法与Search函数的做法类似，但要求在从根结点往下搜索过程中，用指针q记录下当前元素的双亲结点。 如果在搜索中，遇到相同关键字值的元素，则表明有重复元素，那么显示Duplicate信息。 (2)插入新元素 如果二叉搜索树是空树，则新元素e成为树根。如果e的关键字值小于q结点的值，则将新元素e作为q的左孩子，否则作为其右孩子。AVL树：一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。（每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance 。）(详见PPT unit5-2 4)AVL树的插入（详见PPT unit5-2）在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 |balance| 1，则出现了不平衡，需要做平衡化处理。 在AVL树上定义了重载操作“”和“”，以及中序遍历的算法。利用这些操作可以执行AVL树的建立和结点数据的输出。 算法从一棵空树开始，通过输入一系列对象的关键码，逐步建立AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。AVL树的删除如果被删结点x最多只有一个子女，那么问题比较简单。如果被删结点x有两个子女，首先搜索 x 在中序次序下的直接前驱 y (同样可以找直接后继)。再把 结点y 的内容传送给结点x，现在问题转移到删除结点 y。把结点y当作被删结点x。 将结点x从树中删去。因为结点x最多有一个子女，我们可以简单地把x的双亲结点中原来指向x的指针改指到这个子女结点；如果结点x没有子女，x双亲结点的相应指针置为NULL。然后将原来以结点x为根的子树的高度减1。5.什么是树中的路径？什么是图中的路径？怎样利用递归算法计算路径长度？树中的路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。路径长度：路径上的分支数。 树的路径长度是从根到树中每一个结点的路径长度之和。(详见PPT unit4-2 25)图中的路径：在无向图G中，若从顶点vp到vq之间存在顶点序列vp, v1,v2,vn,vq,使得(vp,v1),(v1,v2),(vn , vq )都是图G中的边。对于有向图顶点序列vp,v1,v2,vn,vq,应使, ,都是图G中的边。路径长度: 指路径上边的数目。(详见PPT unit7-1 11)6. 什么是链表？怎样完成插入和删除操作？用链接方式表示的线性表为链表(详见PPT unit2 29)插入和删除操作详见PPT unit2 38-437. 什么是逻辑结构？什么是存储结构？有哪几种典型的逻辑结构和存储结构？逻辑结构：数据元素之间的逻辑关系。集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系；线性结构：结构中的数据元素之间存在一对一的关系；树形结构：结构中的数据元素之间存在一对多的关系；图结构：结构中的数据元素之间存在多对多的关系。(详见PPT unit1 12)存储结构：逻辑结构在存储器中的映象。数据的存储结构：“数据元素”的存储；“关系”的存储数据元素的存储方法 用二进制位(bit)的位串表示数据元素e.g.(321)10 = (101000001)2 A = (001000001)2关系的存储方法顺序存储：以相对的存储位置表示后继关系链式存储：以附加信息(指针)表示后继关系(详见PPT unit1 15-16)8. 什么是栈、队列？它们有哪些典型的使用场合？栈的定义：栈是限定插入和删除操作都在表的一端进行的线性表。若栈中无元素，则为空栈。 允许插入和删除元素的一端称为栈顶，另一端称为栈底。S=(a1,a2,an) （栈的应用详见PPT unit 3）队列是限定在表的一端插入，在表的另一端删除的线性表。若队列中无元素，则为空队列。 队尾允许插入元素的一端 队头允许删除元素的另一端Q=(a1,a2,an) （队列栈的应用详见PPT unit 3）9. 什么是循环链表？什么是循环队列？它们有什么区别？循环链表：不带表头结点的单循环链表(详见PPT unit2 45)循环队列：把数组从逻辑上看成是一个头尾相连的环。(详见PPT unit3 36)10. 什么是算法复杂度？什么是复杂度分析？算法的空间复杂度：是程序运行从开始到结束所需的存储量。渐近时间复杂度：使用大O记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。 (详见PPT unit1 86-93)11. 什么是拓扑排序？拓扑排序算法怎样进行?拓扑排序是求解网络问题所需的主要算法，PERT (Program Evaluation and Review Technique，计划评审技术)和CPM (Critical Path Method，关键路径法)都要用到。(详见PPT unit7-2 5)拓扑排序算法： 1）在图中找一个入度为零的顶点，输出之；2）从图中删除该顶点及其所有出边（产生新的入度为零的顶点）3）重复(1)、(2)，直到所有顶点都输出，或图中剩下的顶点再也没有入度为零的顶点(存在有向回路)为止。(详见PPT unit7-2 8)12.怎样实现链式栈和链式队列？栈的链接表示法（链式栈）：链式栈的定义和操作的实现类似于单链表，请自行实现之。不带表头结点的单链表(详见PPT unit3 14及以前)队列的链接表示法（链式队列）： 链式栈的定义和操作的实现类似于单链表，留作作业，请实现之。不带表头结点的单链表（详见PPT unit3 46及以前）（自行看作业）13.选择排序、堆排序、冒泡排序、快速排序、Shell排序算法是怎样进行的？简单选择排序：该方法的基本思想是：第1趟在初始序列(A0An-1)中找一个最小值，与序列中第一个元素A0交换，这样子序列(A0)有序，下一趟排序在子序列(A1An-1)中进行。第i趟排序在子序列(Ai-1An-1)中找最小值元素与子序列中第一个元素Ai-1交换。进过n-1趟排序后使得初始序列有序。(详见PPT unit6 8)冒泡排序：它的思想是：第1趟在序列(A0An-1)中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次。第1趟排序结束，最大元素被交换到An-1中(即沉底)。下一趟排序只需在子序列(A0An-2)中进行。如果在某一趟排序中未交换元素，说明子序列已经有序，则不再进行下一趟排序。即两两比较，小者前移，大者后沉(详见PPT unit6 15)快速排序的基本思想是：对任意给定的序列中元素Rs(关键字为Ks)，经过一趟排序后，将原序列分割成两个子序列，其中，前一个子序列中的所有元素的关键字均小于等于Ks,后一个子序列中元素的关键字均大于等于Ks。我们称元素Rs 为分割元素 以后只需对2个子序列分别以同样的算法进行快速排序，直到子序列为空或只有一个元素时得到有序序列。由算法概述可看出这个算法可以用递归来实现。(详见PPT unit6 20)堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法 FilterDown( ) 形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。(详见PPT unit6 32)希尔排序（Shell排序）方法又称为缩小增量排序。该方法的基本思想是：设待排序对象序列有 n 个对象，首先取一个整数 gap 1，则该结点的双亲的序号为i/2，当i=1时，该结点为二叉树的根; (2) 若2in，则该结点的左孩子的序号为2i，否则该结点无左孩子。 若2i+1n，则该结点的右孩子的序号为2i+1，否则该结点无右孩子.(详见PPT unit4-1 14)18.在树中，结点数与边数之间有什么关系？怎样计算各种不同度的结点个数之间的关系？结点数与边数之间的关系请自行总结各种不同度的结点个数之间的关系：任意一棵二叉树中，若叶结点的个数为n0，度为2的结点的个数为n2，则必有n0=n2+1。 设二叉树的度为1的结点数为n1，树中结点总数为n，则n=n0+n1+n2。除根结点没有双亲外，每个结点都有且仅有一个双亲，所以有n-1=n1+2n2作为孩子的结点。因此有n0=n2+1，结论成立。19.什么是散列表？典型的散列函数有哪些？散列表要解决的主要问题是什么？散列函数：反映元素的关键字(key)与其在结构中的存储位置(loc)之间的关系的函数(h)，即loc(key)=h(key)散列表(hash,哈希表)：用散列函数建立起来的表。 为建立散列表，(1)首先需要确定散列函数。(2)根据散列函数，可计算出关键字在散列表中的地址，从而可将集合中的元素映射到散列表中。(详见PPT unit5-2 105)“好”的散列函数：(1)均分布，少冲突；(2)计算简便，快速。(1)除留余数法（最常用）：h(key)=key % M (M为散列表表长) 一般取不超过M的素数P更好。(2)平方取中法：h(key)=(key)2的中间若干位k 其中：位数k应满足：10k-1n10k ，n为集合中元素个数。(3) 分段法：a)分段相加法h(key)=关键字分成位数相同的若干段相加 b)分段折叠相加法h(key)=关键字分成位数相同的若干段折叠相加 取的位数与散列表地址位数相同，若和超过指定的位数，则去掉最高位。(4) 数字分析法：取分布均匀的若干位。(详见PPT unit5-2 108-111)20. 树和二叉树有何不同？怎样在树和二叉树之间进行转换？二叉树有哪几种典型的形状？树不能为空，而二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，这是二叉树与树的最主要的差别。(详见PPT unit4-1 10)典型的二叉树：二叉搜索树，二叉平衡树，满二叉树，完全二叉树（自己写的 可能还有别的 ）多叉树转二叉树：多叉树的根结点为二叉树的根，多叉树的结点的第一个儿子变成二叉树对应结点的左孩子，多叉树的结点的右兄弟（出自百度）21. 归并排序、插入排序算法是怎样执行的？归并排序的基本思想是：(1)初始时，将有n个元素的序列看成是n个长度为1的有序子序列，(2)然后两两合并子序列，得到n/2个长度为2或1的有序子序列；再两两合并，直到得到一个长度为n的有序序列时结束。(详见PPT unit6 28)插入排序算法方法的基本思想是：将序列中第1个元素作为一个有序序列，然后将剩下的n-1个元素按关键字大小依次插入该有序序列，经过n-1趟排序后即成为有序序列。(详见PPT unit6 12)22. 在顺序表上和链表上进行插入和删除操作的算法复杂度是多少 ？顺序表上插入渐近时间复杂度：O(n)顺序表上删除渐近时间复杂度：O(n)链表上插入渐近时间复杂度：O(n)链表上删除渐近时间复杂度：O(n) (详见PPT unit2 28 39 41)23. 什么是图的广度优先遍历和深度优先遍历？如何实现算法？从图G中某个顶点v出发,对图进行深度优先搜索（Depth First Search，即DFS）的算法如下： 1. 访问顶点v并打上标记。 2. 依次从v的未访问过的邻接点出发，深度优先搜索图G.(详见PPT unit7-1 39)从图中任一顶点v出发对图进行广度优先搜索（Breadth First Search，即BFS ）的算法的描述: 1 访问顶点v并打上标记; 2 依次访问顶点v的所有未访问的邻接点w1，w2，wt ，再访问与这些w1，w2，wt邻接的所有未访问的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。 3 若图中还有顶点未被访问，则另选一个未访问的顶点， 重新开始上述过程。(详见PPT unit7-1 43)（程序详见PPT unit7-1）24.什么是顺序搜索？有什么特点？线性表的顺序搜索算法 一般的线性表中元素并不要求按关键字值排序。在线性表上搜索指定关键字值的元素的搜索方法只能是顺序搜索。(详见PPT unit5-1 6-13)25.什么是二分查找？什么是对半查找？什么是对半查找的二叉判定树？有序表的二分搜索 当有序表采用顺序方式存储时，可以采用二分搜索的方法搜索指定关键字值的记录在表中的位置。（a1,a2,an） 二分搜索的基本思想是：在确定待查元素X的位置时，先选择表中某一位置i的元素（即分割点），设元素ai 的关键字值为 Ki，将 Ki 与待查元素的关键字值 X 比较。 比较结果有三种可能性： （1)XKi: 若关键字值为X的元素在表中，则必定在子表（ai+1,ai+2,an）中，可以在子表中继续进行二分搜索。(详见PPT unit5-1 14)对半搜索是二分搜索中的一种。分割点为表的中点元素。若当前搜索的子表为（alow,alow+1,ahigh）则i=(low+high)/2其中，i、low 和 high均为元素在表中的序号，low表示表的左端，high表示表的右端。 (详见PPT unit5-1 15)二叉判定树的建立：(1)根结点：第一次比较的元素的结点； (2)结点的序号：元素的序号；(3)根结点左子树的根结点：左边子表第一次比较的元素的结点；(4)根结点右子树的根结点：右边子表第一次比较的元素的结点；(5)：内结点(6) ：外结点；等于其父结点的序号减1(左孩子)； 或等于其父结点的序号(右孩子);(7)从根结点到内结点的路径代表一条搜索路径。搜索成功，算法在内结点处终止；否则在外结点处终止。(详见PPT unit5-1 20)26.什么是图中的最短路径？怎样求最短路径？最短路径通常是针对有向网络而言的。即边上带有权值的有向图。假定G是一个有向网络，每条边上带有一个非负的权值，则从顶点v到顶点w的最短路径指的是从顶点v到顶点w的所有路径中权值之和最小的路径。顶点v称做源点，顶点w称做终点。(详见PPT unit7-2 25)Dijkstra算法（求最短路径）依最短路径的长度递增的次序求得各条路径。设置一个集合S，该集合中存放从给定源点出发最短路径已知的所有顶点。因此算法开始时，集合S中只有源点一个顶点。随着算法的进行，其余的顶点被逐步加入集合S。因此算法要解决的问题是确定每步应该加入哪个顶点？设定一个数组int distancegraph_size;记录从源点到其它顶点的距离。若顶点v已在S中，则distancev记录了从源点到顶点v的最短距离。若顶点v还未加入S中，则distancev记录了从源点到某个S中的顶点w的最短距离加上边的权值。distance数组的初始化。 (1)若从源点邻接到顶点v(有边的情况)，则distancev即为该边的权值。(2)否则(无边的情况)，则distancev为无穷大。算法进行时，从distance中找一个最小值，并将其对应的顶点加入到S中。一旦某顶点v加入S，则重新计算尚未加入S的顶点所对应的数组distance元素值。更新规则为：若distancew distancev+weight()，令distancew = distancev+weight()如此循环往复，直到把所有顶点加入S。(详见PPT unit7-2 27-29)27. 什么是索引？什么是稠密索引？什么是稀疏索引？稠密索引：一个索引项对应数据表中一个对象的索引结构。当对象在外存中按加入顺序存放而不是按关键码有序存放时必须采用稠密索引结构，这时的索引结构叫做索引非顺序结构。稀疏索引：当对象在外存中有序存放时，可以把所有 n 个对象分为 b 个子表(块)存放，一个索引项对应