数据结构期末复习提纲

第1-3章绪论1复习范围：第一、二、三章所有内容2复习要点：1）数据结构的基本概念逻辑结构：表，树，图存储结构：顺序（静态），链式（动态），索引，Hash2）算法和算法分析计算算法的时间复杂度和空间复杂度的方法第四章线性表、栈、队列1复习范围：第四章所有内容2线性表复习要点：1）线性表的逻辑结构2）线性表的存储结构：顺序：数组，表长表示链式：单链表，循环链表，双向链表，头指针，头结点，首结点，空标志，结束标志3）插入和删除算法遍历方法：i++p=p-next算法实现:元素移动指针调整算法的时间复杂度第四章线性表、栈、队列（续）3栈、队列复习要点：1）栈的定义，特性（LIFO），存储结构2）POP和PUSH算法3）栈的空、满标志4）队列的定义，特性（FIFO）5）链式队列和循环队列的存储结构6）队列的入队和出队算法7）队列的空、满标志8）堆栈应用，举例：表达式求值：A*(B+C)-D1复习范围：PPT2复习要点：1）数组的逻辑结构2）以行或列为主序的存储结构及地址计算3）对特殊矩阵压缩存储的下标变换方法4）稀疏矩阵的三元组表示和十字链表表示方法5）广义表的定义、特点和存储结构（附加）数组与广义表第五、六章二叉树和普通树1复习范围：第五章、第六章2复习要点：1）树的递归形式的定义和其他术语2）二叉树的定义，形态，五条性质及其证明，存储结构3）二叉树的遍历：求遍历序列，遍历算法，由两种遍历序列恢复二叉树4）树与森林：存储结构，与二叉树的转换，先根和后根遍历，由两种遍历序列恢复树或森林5）哈夫曼树：带权路径长度，最优二叉树的定义，构造方法，哈夫曼编码的方法第七章图1复习范围：第七章2复习要点：1）概念术语：图与网（有向、无向），顶点与边（弧），邻接与度，路径，连通，生成树2）图的邻接矩阵或邻接表的表示，求顶点度的算法，求顶点的边或弧的算法3）图的DFS、BFS遍历序列4）无向图的DFS，BFS生成树5）利用Prim算法和Kruskal算法的基本方法求无向网的最小生成树6）利用Dijkstra算法求最短路径第八章内部排序1复习范围：第八章2复习要点：1）概念术语：排序，排序的分类，稳定性2）基本排序算法：直接插入、起泡、简单选择排序的算法实现，效率分析（关键字的比较次数和元素的移动次数）3）先进排序方法：Shell、快速、堆、归并、基数排序的方法和执行过程，堆的调整方法第九、十章查找、索引1复习范围：第九章、第十章2复习要点：1）概念术语：查找表、关键字、查找成功（失败）2）线性表查找：顺序、自组织表、折半算法实现，对存储结构的要求，平均查找长度计算。判定树概念。3）Hash表：Hash函数及其构造方法，冲突及其解决方法，Hash表的查找、插入、删除过程，平均查找长度4）索引查找：线性索引表、分块索引表。5）二叉排序树的定义，查找算法，插入和删除算法，平均查找长度6）AVL树的定义，构造过程，插入删除旋转类型与方法7）2-3树（B-树）的定义，查找、插入、删除的方法考试常见题型(复习提纲)第一部分：概念、线性表、栈和队列----线性结构．算法的五个重要特性?．算法的时间复杂度、空间复杂度?．线性表的元素关系存储时如何体现？．头结点的作用？首结点、头结点、头指针区别？.单链表、双链表、循环链表的插入和删除操作,以及判断链表为空的条件？．循环队列Q[0，n-1]，头、尾位置为f、r，队满、队空的条件？队列元素个数计算？．双端队列、单端受限队列的入队与出队序列关系？.元素进栈与退栈的过程？对已知入栈序列，可能输出结果及不可能输出结果？考试常见题型(复习提纲)第二部分：二叉树与普通树---树形结构．树的表示形式？二叉树的性质？二叉树的存储结构？二叉树的四种遍历？.具有n个结点的二叉树的最小深度？最大深度？．n个结点的完全二叉树顺序存储，叶结点和非叶结点的个数、范围？．遍历方式不同叶结点的相对顺序如何？内结点的相对顺序又如何？.已知二叉树的两种遍历结果（一般必须包含一个中序或层序），请构造这棵二叉树？.树的存储结构有哪些？树和森林与二叉树的相互转换？（即对一棵树或森林给出二叉链表存储？根据二叉链表存储画出该树或森林？）.已知电文，求哈夫曼编码需要位数和具体编码数？对已知序列进行哈夫曼编码？.设二叉树采用二叉链表存储，请编写算法实现求二叉树高度(结点个数，判定是否为平衡二叉树，是否为二叉排序树,AVL树的构造等)？考试常见题型(复习提纲)第三部分：图---图形结构．无向图和有向图的存储方法（主要有2种）？．图的遍历（深度优先和广度优先）？图的遍历结果与存储结构有关！.图的生成树？带权图的最小生成树？.有向图可以进行拓扑排序的条件？对一个图进行拓扑排序？.对已知带权有向图，求关键路径？计算某源点都其余顶点的最短路径？.比如，已知一个无向图的邻接表（1）请画出该无向图；（2）根据邻接表，分别写出用DFS和BFS算法从顶点v0开始的遍历该图后所得到的遍历序列，并画出DFS生成树和BFS生成树。考试常见题型(复习提纲)第四部分：排序---数据结构的应用．排序算法的稳定性？对各种排序法中“排序趟”的概念？.两类排序中主要排序方法有哪些？对已知序列，可按给定排序方法给出第i趟结果？.不稳定的排序算法有那些？.插入、简单选择、冒泡排序算法的主要工作量是什么？．用筛法建堆则必须从什么位置开始？堆是一个数据结构吗？.判断已知序列是否为堆？如不是，请用筛选建堆？．初始数据如果已有序，耗费的时间反而最多的算法？．对已知序列找出前5个最小的元素用什么算法？.做快速排序，请给出第i趟的结果及元素交换次数?.做Shell排序，步长已知，请给出第i趟结果?.对已知序列,请给出归并排序第i趟的结果？考试常见题型(复习提纲)第四部分：查找---数据结构的应用．顺序查找方法适宜于存储结构？．线性表顺序查找不成功时关键字的比较次数?.有序表的折半查找过程？查找过程的判定树？．分块查找(索引表查找)的T(n)的组成及意义？.二叉排序树的形成与查找？如：对同一组数据而言二叉排序树是否唯一的?对二叉排序树先删去x再插入x，新旧二叉排序树相同？构建二叉排序树，请画出第i步?.平衡二叉树的平衡调整（4种）？如：对已知序列构造平衡二叉树，如有旋转请画出旋转前、后的树形结构并标注旋转类型?考试常见题型(复习提纲)第四部分：查找---数据结构的应用．B树的元素插入与删除？如：对已知序列，画出一个m阶Ｂ-树？.高为3的5阶B-树（连叶层在内）最少的关键字总数目?.哈希表（散列表）中散列函数构造与冲突解决方法？如：已知序列，设散列函数H(k)=kmod7，用线性探测法解决冲突。请建散列表存储及查找次数？例题：1、以下术语与数据的存储结构无关的有哪些?A、栈B、hash表C、线索树D、双链表2、对包含n个元素的hash表进行检索，平均检索长度为：A、O(log2n)B、O(n)C、O(nlog2n)D、不直接依赖于n3、对线性表进行二分法查找，其前提条件是：A、线性表以顺序方式存储，并且按关键码值的检索频率排好序；B、线性表以顺序方式存储，并且按关键码值排好序；C、线性表以链接方式存储，并且按关键码值排好序；D、线性表以链接方式存储，并且按关键码值的检索频率排好序；【答案】1、A2、D3、B4、画出对长度为10的有序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。(分析)【分析】假设分别用1至10表示表中的10个结点，要画出对此有序表进行折半查找的判定树，须进行折半查找的过程，用第一次得到的mid结点5作为判定树的根结点，用后面得到的两个mid结点2和8为根结点构造根结点的两棵子树，…根据判定树，平均查找长度即为各层的结点数和其所在层次数乘积的累加和。【解答】判定树如图所示。等概率时查找成功的平均查找长度ASLsucc=(1*1+2*2+3*4+4*3)/10=29/1057496318210例题：5、在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用二分法查找关键码值11,所需的关键码比较次数为().A、2B、3C、4D、56、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是()A、分块法B、顺序法C、二分法D、hash法7、顺序查找法适合于存储结构为（）的线性表。A、hash存储B、压缩存储C、索引存储D、顺序存储或链接存储【答案】5、C6、D7、D8、采用分块查找时，若线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分______个结点最佳。A、16B、64C、128D、2569、5层结点的AVL树至少有()个结点。(推导方法)A、10B、12C、15D、1710、哈希查找中k个关键字具有同一hash函数值，若用线性探测法把这k个关键字值存入到hash表中，至少要进行（）次探测。A、kB、k+1C、k(k+1)/2+1D、k(k+1)/2【答案】8、A9、B10、D11、设有一组关键字{11，54，36，89，51，47，38，59，63，94，15}，采用hash函数：H(key)=key%13。采用开放地址法的线性探测再hash方法解决冲突，试在0…15的hash地址空间中对该关键字序列构造hash表，并求在等概率下查找成功的ASL。(分析)【分析】依题意，m=16，线性探测再hash的地址计算公式为：d1=H(key)=key%13，dj=(dj-1+1)%m=(dj-1+1)%16;其中j=2，3，4，…要计算平均查找长度，须计算出查找每个关键字时的比较次数，即再hash次数加1。例如，H(51)=51%13=11，冲突；H(51)=(11+1)%16=12，仍冲突；H(51)=(12+1)%16=13，不冲突，则查找关键字51时的比较次数为2+1=3。【解答】各关键字的hash地址计算如下表所示：数组下标0123456789101112131415数组元素5494155947361189513863比较次数11311112335在等概率下查找成功的平均查找长度为：ASLsucc=(1*5+2*1+3*3+5*1)/11=21/11例题：⒈在图中，所有顶点的度数之和等于所有边数的（）倍。A、1/2B、1C、2D、4⒉在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、1/2B、1C、2D、4⒊一个有n个顶点的无向图最多有（）条边。A、nB、n(n-1)C、n(n-1)/2D、2n⒋具有4个顶点的有向完全图有（）条边。A、6B、12C、16D、20【答案】1、C2、B3、C4、B例题：⒌对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）：A、nB、(n-1)2C、n-1D、n2⒍已知一个图如图所示，若从顶点a出发按深度搜索发进行遍历，则可能得到的一种顶点序列为（①）；按广度搜索法进行遍历，则可能得到的一种顶点序列为（②）。①A、abecdfB、acfebdC、aebcfdD、aedfcb②A、abcedfB、abcefdC、aebcfdD、acfdeb【答案】5、D6、①D②Babcedf例题：7、下面关于图的存储的叙述中正确的是A、用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关B、用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关C、用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关D、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关【答案】7、A例题：8、对于右边的有向图：（1）可能的拓扑序列为（）A、abcdefB、aebcdfC、abcfedD、abedcf（2）可以排成多少个不同的拓扑序列（）A、2B、3C、4D、5【答案】8、(1)D8、(2)Bbacedf例题：1、设有500个元素的无序向量表，希望用最快的速度取出前10个最小元素，请问用下列哪一种方法最好？为什么？快速排序、堆排序、归并排序、shell排序。【答案】1、采