数据结构期末复习提纲ppt课件.ppt

《数据结构期末复习提纲ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构期末复习提纲ppt课件.ppt（45页珍藏版）》请在三一办公上搜索。

1、第1-3章 绪 论,1 复习范围：第一、二、三章所有内容2 复习要点： 1）数据结构的基本概念 逻辑结构：表，树，图 存储结构：顺序（静态），链式（动态），索引，Hash 2） 算法和算法分析 计算算法的时间复杂度和空间复杂度的方法,第四章 线性表、栈、队列,1 复习范围：第四章所有内容2 线性表复习要点： 1）线性表的逻辑结构 2）线性表的存储结构： 顺序：数组，表长表示 链式：单链表，循环链表，双向链表，头指针， 头结点，首结点，空标志，结束标志 3）插入和删除算法遍历方法： i+ p=p-next 算法实现: 元素移动 指针调整 算法的时间复杂度,第四章 线性表、栈、队列（续）,3 栈、

2、队列复习要点： 1）栈的定义，特性（LIFO），存储结构 2）POP和PUSH算法 3）栈的空、满标志 4）队列的定义，特性（FIFO） 5）链式队列和循环队列的存储结构 6）队列的入队和出队算法 7）队列的空、满标志 8）堆栈应用，举例：表达式求值：A*(B+C)-D,1 复习范围：PPT2 复习要点： 1）数组的逻辑结构 2）以行或列为主序的存储结构及地址计算 3）对特殊矩阵压缩存储的下标变换方法 4）稀疏矩阵的三元组表示和十字链表表示方法 5）广义表的定义、特点和存储结构,（附加）数组与广义表,第五、六章 二叉树和普通树,1 复习范围：第五章、第六章2 复习要点： 1）树的递归形式的定义

3、和其他术语 2）二叉树的定义，形态，五条性质及其证明，存储结构 3）二叉树的遍历：求遍历序列，遍历算法，由两种遍历序列恢复二叉树 4）树与森林：存储结构，与二叉树的转换，先根和后根遍历，由两种遍历序列恢复树或森林 5）哈夫曼树：带权路径长度，最优二叉树的定义，构造方法，哈夫曼编码的方法,第七章 图,1 复习范围：第七章2 复习要点： 1）概念术语：图与网（有向、无向），顶点与边（弧），邻接与度，路径，连通，生成树 2）图的邻接矩阵或邻接表的表示，求顶点度的算法，求顶点的边或弧的算法 3）图的DFS、BFS遍历序列 4）无向图的DFS，BFS生成树 5）利用Prim算法和Kruskal算法的基本

4、方法求无向网的最小生成树 6）利用Dijkstra算法求最短路径,第八章 内部排序,1 复习范围：第八章2 复习要点： 1）概念术语：排序，排序的分类，稳定性 2）基本排序算法：直接插入、起泡、简单选择排序的算法实现，效率分析（关键字的比较次数和元素的移动次数） 3）先进排序方法：Shell、快速、堆、归并、基数排序的方法和执行过程，堆的调整方法,第九、十章 查找、索引,1 复习范围：第九章、第十章2 复习要点： 1）概念术语：查找表、关键字、查找成功（失败） 2）线性表查找：顺序、自组织表、折半算法实现，对存储结构的要求，平均查找长度计算。判定树概念。 3）Hash表： Hash函数及其构造

5、方法，冲突及其解决方法， Hash表的查找、插入、删除过程，平均查找长度 4）索引查找：线性索引表、分块索引表。 5）二叉排序树的定义，查找算法，插入和删除算法，平均查找长度 6）AVL树的定义，构造过程，插入删除旋转类型与方法 7）2-3树（B-树）的定义，查找、插入、删除的方法,考试常见题型(复习提纲),第一部分：概念、线性表、栈和队列-线性结构算法的五个重要特性?算法的时间复杂度、空间复杂度?线性表的元素关系存储时如何体现？头结点的作用？首结点、头结点、头指针区别？. 单链表、双链表、循环链表的插入和删除操作,以及判断链表为空的条件？循环队列Q0，n-1，头、尾位置为f、r，队满、队空的

6、条件？队列元素个数计算？ 双端队列、单端受限队列的入队与出队序列关系？. 元素进栈与退栈的过程？对已知入栈序列，可能输出结果及不可能输出结果？,考试常见题型(复习提纲),第二部分：二叉树与普通树-树形结构树的表示形式？二叉树的性质？二叉树的存储结构？二叉树的四种遍历？. 具有n个结点的二叉树的最小深度？最大深度？n个结点的完全二叉树顺序存储，叶结点和非叶结点的个数、范围？遍历方式不同叶结点的相对顺序如何？内结点的相对顺序又如何？. 已知二叉树的两种遍历结果（一般必须包含一个中序或层序），请构造这棵二叉树？. 树的存储结构有哪些？树和森林与二叉树的相互转换？（即对一棵树或森林给出二叉链表存储？根

7、据二叉链表存储画出该树或森林？）. 已知电文，求哈夫曼编码需要位数和具体编码数？对已知序列进行哈夫曼编码？. 设二叉树采用二叉链表存储，请编写算法实现求二叉树高度(结点个数，判定是否为平衡二叉树，是否为二叉排序树,AVL树的构造等)？,考试常见题型(复习提纲),第三部分：图-图形结构无向图和有向图的存储方法（主要有2种）？ 图的遍历（深度优先和广度优先）？图的遍历结果与存储结构有关！. 图的生成树？带权图的最小生成树？. 有向图可以进行拓扑排序的条件？对一个图进行拓扑排序？. 对已知带权有向图，求关键路径？计算某源点都其余顶点的最短路径？ .比如，已知一个无向图的邻接表（1）请画出该无向图；（

8、2）根据邻接表，分别写出用DFS和BFS算法从顶点v0开始的遍历该图后所得到的遍历序列，并画出DFS生成树和BFS生成树。,考试常见题型(复习提纲),第四部分：排序-数据结构的应用排序算法的稳定性？对各种排序法中“排序趟”的概念？. 两类排序中主要排序方法有哪些？对已知序列，可按给定排序方法给出第i趟结果？. 不稳定的排序算法有那些？. 插入、简单选择、冒泡排序算法的主要工作量是什么？用筛法建堆则必须从什么位置开始？堆是一个数据结构吗？. 判断已知序列是否为堆？如不是，请用筛选建堆？初始数据如果已有序，耗费的时间反而最多的算法？对已知序列找出前5个最小的元素用什么算法？. 做快速排序，请给出第

9、i趟的结果及元素交换次数?. 做Shell排序，步长已知，请给出第i趟结果?. 对已知序列,请给出归并排序第i趟的结果？,考试常见题型(复习提纲),第四部分：查找-数据结构的应用顺序查找方法适宜于存储结构？线性表顺序查找不成功时关键字的比较次数? . 有序表的折半查找过程？查找过程的判定树？分块查找(索引表查找)的T(n)的组成及意义？. 二叉排序树的形成与查找？如：对同一组数据而言二叉排序树是否唯一的? 对二叉排序树先删去x再插入x，新旧二叉排序树相同？构建二叉排序树，请画出第i步?. 平衡二叉树的平衡调整（4种）？如：对已知序列构造平衡二叉树，如有旋转请画出旋转前、后的树形结构并标注旋转类

10、型?,考试常见题型(复习提纲),第四部分：查找-数据结构的应用B树的元素插入与删除？如：对已知序列，画出一个m阶-树？. 高为3的5阶B-树（连叶层在内）最少的关键字总数目?. 哈希表（散列表）中散列函数构造与冲突解决方法？如：已知序列，设散列函数H(k)= k mod 7，用线性探测法解决冲突。请建散列表存储及查找次数？,例题：1、以下术语与数据的存储结构无关的有哪些? A、栈 B、hash表 C、线索树 D、双链表 2、对包含n个元素的hash表进行检索，平均检索长度为： A、O(log2n) B、O(n) C、O(nlog2n) D、不直接依赖于n3、对线性表进行二分法查找，其前提条件是

11、 ： A、线性表以顺序方式存储，并且按关键码值的检索 频率排好序； B、线性表以顺序方式存储，并且按关键码值排好序； C、线性表以链接方式存储，并且按关键码值排好序； D、线性表以链接方式存储，并且按关键码值的检索 频率排好序；,【答案】 1、A 2、D 3、B,4、画出对长度为10的有序表进行折半查找的一棵判定树， 并求其等概率时查找成功的平均查找长度。 (分析),【分析】 假设分别用1至10表示表中的10个结点，要画出对此有序表进行折半查找的判定树，须进行折半查找的过程，用第一次得到的mid结点5作为判定树的根结点，用后面得到的两个mid结点2和8为根结点构造根结点的两棵子树， 根据判定树

12、，平均查找长度即为各层的结点数和其所在层次数乘积的累加和。,【解答】 判定树如图所示。等概率时查找成功的平均查找长度 ASL succ =(1*1+2*2+3*4+4*3)/10 = 29/10,例题：5、在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用二分法查找关键码值11, 所需的关键码比较次数为( ). A、2 B、 3 C、 4 D、 5 6、如果要求一个线性表既能较快地查找，又能适应动态变化 的要求，则可采用的方法是 ( ) A、分块法 B、顺序法 C、二分法 D、hash法 7、顺序查找法适合于存储结构为（ ）的线性表。 A、hash存储 B 、 压缩存

13、储 C 、索引存储 D 、顺序存储或链接存储,【答案】 5、 C 6、D 7、D,8、采用分块查找时，若线性表中共有256个元素，查找每个 元素的概率相同，假设采用顺序查找来确定结点所在的 块时，每块应分_个结点最佳。 A 、 16 B 、 64 C 、 128 D 、 256 9、5层结点的AVL树至少有( )个结点。(推导方法) A 、 10 B 、 12 C 、 15 D 、 17 10、哈希查找中k个关键字具有同一hash函数值，若用线性 探测法把这k个关键字值存入到hash表中，至少要进行 （ ）次探测。 A 、k B 、k+1 C 、k(k+1)/2+1 D 、k(k+1)/2,【

14、答案】 8、A 9、 B 10、D,11、设有一组关键字11，54，36，89，51，47，38，59，63，94，15，采用hash函数：H(key) = key % 13。采用开放地址法的线性探测再hash方法解决冲突，试在015的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

15、次数加1。例如，H(51) = 51 % 13 = 11，冲突；H(51) = (11+1) % 16 = 12 ，仍冲突；H(51) = (12+1) % 16 = 13，不冲突，则查找关键字51时的比较次数为2+1 = 3。,在等概率下查找成功的平均查找长度为：ASLsucc = (1*5 + 2*1 +3*3 + 5*1)/11 = 21/11,例题： 在图中，所有顶点的度数之和等于所有边数的（ ）倍。 A、1/2 B、1 C、2 D、4 在一个有向图中，所有顶点的入度之和等于所有顶点的出度 之和的（ ）倍。 A、1/2 B、1 C、2 D、4 一个有n个顶点的无向图最多有（ ）条边。

16、A、n B、n(n-1) C、n(n-1)/2 D、2n 具有4个顶点的有向完全图有（ ）条边。 A、6 B、12 C、16 D、20,【答案】 1、C 2、B 3、C 4、B,例题： 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）： A、n B、(n-1)2 C、n-1 D、n2 已知一个图如图所示，若从顶点a出发按深度搜索发进行遍历，则可能得到的一种顶点序列为（ ）；按广度搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A、abecdf B、acfebd C、aebcfd D、aedfcbA、abcedf B、abcefd C、aebcfd D、acfdeb,【

17、答案】 5、D 6、 D B,例题：7、下面关于图的存储的叙述中正确的是 A、用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关 B、用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 C、用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关 D、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关,【答案】 7、A,例题：8、 对于右边的有向图：（1）可能的拓扑序列为（ ） A、abcdef B、aebcdf C、abcfed D、abedcf（2）可以排成多少个不同的拓扑序列（ ） A、2 B、3 C、4 D、

18、5,【答案】 8、(1) D 8、(2) B,例题：1、 设有500个元素的无序向量表，希望用最快的速度取出前10个最小元素，请问用下列哪一种方法最好？为什么？ 快速排序、堆排序、归并排序、shell排序。,【答案】1、采用堆排序最好，因为堆排序每次都能取出一个最小元素来，而其他的排序都必须在排序结束后才能确定向量中元素的次序。,2、在所有的排序方法中，关键字比较的次数与向量表中初始排列次序无关的是( )。 A、shell排序 B、冒泡排序 C、选择排序 D、快速排序3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A、插入排序 B、选择排序 C、快速排序 D、归并排序4、

19、下列排序方法中，要求内存开销最大的是( )。 A、插入排序 B、选择排序 C、快速排序 D、归并排序5、快速排序最坏的情况是( )。 A、基本无序 B、数据的量多 C、基本有序 D、数据的量少,【答案】 2、B 3、A 4、D 5、C,6、请写出快速排序的非递归算法。,void Quick_Sort(STable R，int l，h) int k； set_null(S)； do while( l = h ) )；,7、 对于5个不同的数据元素进行排序至少需要比较( )次 A、4 B、5 C、6 D、78、 对于n个不同的数据元素进行冒泡排序至少需要比较( )次 A、n2 B、nlog2n C

20、、n D、n-1,【答案】7、A 。因为如果这5个数据是排好序的，采用直接插入排序或冒泡排序方法，比较次数为4次。 8、D。理由与7相同。,9、在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向的移动，从而认为该排序方法是不稳定的，这种说法对吗？为什么？,【答案】 9、所谓排序的稳定性是指排序前两个关键字相等的记录在排序后它们的相对位置不变。题目中没有涉及到记录的相对位置，只提到了移动方向，所以这种说法是不对的。,1、数据结构是一门研究非数值计算的程序设计问题中计算机的_以及它们之间的_和运算等的学科。数据结构被形式地定义为DS=（D, R），其中D是_的有限集合，R是D上的_有限

21、集合。2、数据结构包括数据的_、数据的_和数据的_这三个方面的内容。按逻辑结构可分为两大类，它们分别是_和_。按存储结构可分为四种基本的存储方法表示，它们分别是_、_、索引和Hash。,【答案】 1、操作对象、关系、数据元素、关系 2、逻辑结构、存储结构、运算、线性、非线性,3、设二维数组A-20,30-30,20, 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A25,18的存储地址为_；如按列优先顺序存储,则元素A-18,-25的存储地址为_。 4、已知入栈次序为X、Y、Z，出栈的序列可有_种，形式为_。 5、包含结点A,B,C的二叉树有_种不同的状态，_

22、种不同的二叉树。,【答案】 3、9392；620。 4、5种； XYZ、ZYX、YXZ、YZX、XZY 5、5，30。,6、具有1,000个结点的完全二叉树，有_个叶子结点，有_个度为2的结点，有_个结点只有非空左子树，有_个结点只有非空右子树。7、对于一个有10,000个结点的二叉树，树叶最多有_个；最少有_个。,【答案】 6、500，499，1，0。 7、最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。,8、高度为4的平衡二叉树最多有 个结点，最少有 个结点。9、请分析下面程序片段的时间复杂度。 for(i = 1; i = n; i = i * 2) for(j

23、 = 1; j = i; j+) s+;,【答案】 8、15，9。 9、n的数量级,10、正反读都相同的字符序列称“回文”。 设字符序列已存入计算机，请确定用线性表、栈和队不同的数据结构判别回文问题的可能性及最适宜结构。,【答案】 10、线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可；若正文是单链表形式存储，则需辅助空间，可以从链首开始入栈，全部压入后再依次输出。最适宜数组存储结构。,11、仅用一个数组实现

24、线性表就地逆置的算法，即将（a1,an）逆转为(an,a1),【答案】 11、void reverse(SqList / reverse,12、算法完成什么工作？ int TestA(sqlist ,【答案】 判定A是否为大顶堆（1）/小顶堆（2）。,13、算法复杂度O（1）的含义是什么？14、字符串有几种存储方式？并说明这几种存储方式的特点。,【答案】 13、表示算法复杂度与输入的元素规模无关，是一个常数C（但不一定是1）。或：表示该算法执行时耗时长短或占用空间的多少与元素个数n无关。 14、串有三种存储结构，分别是顺序存储、链式以及堆结构。顺序存储适用于固定长度的串，后两种适用于可变长度的

25、串。,15、已知一森林的先序遍历序列和中序遍历序列分别为：ABCDEFGHIJKL、CBEFDGAJIKLH，求对应的森林？利用性质，首先画出二叉树，在转换成森林。,【答案】,16、对n个元素进行快速排序时，所需的比较次数依赖于这n个元素的初始序列。则：（1）、当n = 7时，在最好的情况下，需要进行多少次比较？（2）、请给出n = 7时最好情况下的初始排列的实例。,【答案】 16、在最好情况下要进行10次比较2趟排序，对第一趟7个元素进行6次比较，对第二趟作2*2次比较。所以一共做10次比较。 最好的初始序列为：4 1 3 2 6 5 7,17、删除结点p在给定链表L的中间，某同学在实现时，忘记了记录结点p的前一个结点，当前指针已经指到了结点p，如果不重新遍历，问该如何操作？,【答案】 17、将后面结点的值给p，删除后面的结点即可。,