《C题库期末复习》课件.ppt

1、BUPT期末复习BUPT1第一章 绪论 数据结构的基本概念和术语 数据、数据元素、数据项、数据对象、数据结构等基本概念 数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系 数据结构的四种逻辑结构及四种常用的存储表示方法 抽象数据类型的概念及其与数据结构的关系BUPT2 算法的描述和分析 算法、算法的时间复杂度和空间复杂度的概念 算法描述和算法分析的方法 BUPT3第二章 线性表线性表的逻辑结构 线性表的逻辑结构特征 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算 BUPT4 线性表的顺序存储结构 顺序表的存储方式及它如何映射线性表中元素之间的逻辑关系 顺序表的存储结构定义 线

2、性表基本运算在顺序表上的实现方法及其时间性能分析 利用顺序表设计算法解决应用问题 BUPT5 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解题思路：在递增有序的顺序表中插入一个元素解题思路：在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素递首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法比顺序查找效率要高。增有序，采用折半查找法比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素后移动一个元素位置，之后将元素x插入即可

3、。假插入即可。假设顺序表设顺序表va存放在数组存放在数组A中（假设下标从中（假设下标从1开开始）。始）。void Insert（ElemType A，int size,ElemType x）。low=1；high=num；/假设下标从1开始 while（lowx）high=mid-1；else low=mid+1；for（i=num；i=low；i-）Ai+1=Ai；元素后移。Ai+1=x；将元素x插入。算法结束 BUPT6 线性表的链式存储结构 链表的存储方式及它如何映射线性表中元素之间的逻辑关系 链表中头指针和头节点的使用 单链表、双链表、循环链表在链接方式上的区别 各种链表的存储结构定义

4、 线性表基本运算在链表上的实现方法及其时间性能分析 循环链表上尾指针取代头指针的作用 利用链表设计算法解决简单的应用问题BUPT7 已知线性表中的元素以值递增有序排列，并以单链表（带头结点）作为存储结构，试写一算法删除表中所有值大于mink且小于maxk的元素。解题思路：首先找到最后一个元素值小于等于解题思路：首先找到最后一个元素值小于等于mink的结点的结点位置（位置（q）；再往后依次删除结点直到第一个值大于等于）；再往后依次删除结点直到第一个值大于等于maxk结点为止。结点为止。void delete(sqlist*la,int mink,int mark)sqlist*p,*q,;q=l

5、a;p=la-next;while(p&p-datanext;while(p&p-datanext;free(p);q-next=p;BUPT8 写出单链表（带头结点）就地逆置算法。void reverse(linklist*h)linklist p,q;p=h-next;h-next=NULL;while(p!=null)q=p;/q指向当前结点 p=p-next;/p指向下一个结点 q-next=h-next;/将*q插入到*h之后 h-next=q;BUPT9 顺序表和链表的比较 顺序表和链表的主要优缺点 根据应用问题的时空要求，为线性表选择合理的存储结构BUPT10第三章 栈与队列栈的

6、逻辑结构，存储结构及其相关算法栈的逻辑结构特点，栈与线性表的关系顺序栈和链栈的存储结构定义顺序栈和链栈上进栈、退栈等基本运算的实现方法栈上的“上溢”和“下溢”的概念及其判别条件递归过程中栈的作用设计递归程序的原则和方法利用栈设计算法解决简单的应用问题 BUPT11 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列

7、中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SSS操作序列；对于合法序列BAC，我们使用SSS操作序列。BUPT12 试证明：若借助栈由输入序列1,2,n得到输出序列为P1,P2,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着ijk,使PjPkPi。如果ij，则对于pipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于ijk，不可能出现pjpkdata=x;s-next

8、=rear-next;/将s结点链入队尾 rear-next=s;rear=s;/rear指向新队尾void DeQueue(LinkedList rear)if(rear-next=rear)printf(“队空n”);exit(0);s=rear-next-next;/s指向队头 rear-next-next=s-next;/队头出队。printf(“出队元素是”，s-data);if(s=rear)rear=rear-next;/空队列 free(s);BUPT15第四章 串 串及其运算 串的概念及其与线性表的关系 串上定义的基本运算，并能利用基本运算构造出较复杂的运算 BUPT16 串

9、的存储结构和基本运算的实现 串的两种主要存储结构顺序串和链串的存储结构定义（C语言的类型描述）顺序串上串的基本运算的实现 朴素的模式匹配算法与朴素的模式匹配算法与KMP算法的算法思想及算法的算法思想及时间复杂度分析时间复杂度分析 KMP算法中算法中next和和nextval数组的求值方法数组的求值方法 BUPT17 求模式串t1=aaab，t2=abcabaa，t3=adabbadada的next和nextval数组值 BUPT18第六章 树 树的概念 树的逻辑结构特征 树的常用术语及含义BUPT19 二叉树 二叉树的定义，二叉树与树的差别 完全二叉树和满二叉树的概念 二叉树的性质 二叉树的顺

10、序存储结构和链式存储结构的定义（C语言的类型描述）和表示方法BUPT20 二叉树的遍历 二叉树的先序、中序、后序、层序遍历算法 求给定二叉树的先序、中序、后序遍历对应的结点访问序列 由二叉树的先序和中序、中序和后序、中序和层序的序列确定二叉树 以遍历算法为基础，设计有关算法解决简单的应用问题BUPT21 线索二叉树 二叉树线索化的目的 线索二叉树存储结构的表示方法 在线索二叉树中查找给定结点的前趋和后继的方法BUPT22 树和森林 树和森林与二叉树之间的转换方法和对应关系 树的各种存储结构的表示方法及其特点 树的先序和后序遍历方法 森林的先序和中序遍历方法BUPT23 哈夫曼树及其应用 最优二

11、叉树的概念及特点 求哈夫曼树的方法 设计哈夫曼编码的方法BUPT24一、下面是用c语言编写的对不带头结点的单链表不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句（不允许使用额外的辅助变量不允许使用额外的辅助变量）。void reverse（linklist&L）p=NULL;q=L;while（q!=NULL）(1);q-next=p;p=q;(2)_;(3)_;二、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（1）下面所示的序列中哪些

12、是合法的？A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回TRUE，否则返回FALSE（假定被判定的操作序列已存入一维数组A中）。BUPT25 三、设模式串t=abcabaa，试求出该模式串的next和nextval数组的值。四、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：A B D F C E G H 中序遍历序列：B F D A G E H C（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）。BUPT26第七章 图

13、 图的概念 图的逻辑结构特征 图的常用术语及含义 图的存储结构 图的邻接矩阵的存储结构定义及表示法和特点 图的邻接表的存储结构定义及表示法和特点 BUPT27 图的遍历 图的深度优先搜索和广度优先搜索遍历算法及时间性能 确定两种遍历所得到的顶点访问序列 图的两种遍历与树的遍历之间的关系 利用图的两种遍历设计算法解决简单的应用问题 BUPT28 生成树和最小生成树 生成树和最小生成树的概念 对给定的图画出深度和广度优先生成树或生成森林 Prim和Kruskal算法的基本思想 对给定的连通图，根据Prim和Kruskal算法构造出最小生成树BUPT29 有向无环图的应用 拓扑排序的基本思想和步骤

14、拓扑排序不成功的原因 求给定AOV网的拓扑序列 关键路径、关键活动的概念 求AOE网的关键路径的步骤和方法 对给定的AOE网，求关键路径和工期BUPT30 最短路径 最短路径的含义 求单源最短路径的Dijkstra算法的基本思想和时间性能 对于给定的有向图，画出根据Dijkstra算法求单源最路径的过程示意图 求每一对顶点间最短路径的Floyd算法的基本思想和时间性能 A(k)i,j(1kn)的含义 对于给定的有向图，用Floyd算法求每一对顶点之间的最短路径长度，能写出A(0)，(1)，(n)的值BUPT311.请给出所示有向图的 1)每个顶点的入/出度；2)邻接矩阵；3)逆邻接表；4)强连

15、通分量。2.画出所示无向图的邻接表，它所 邻接到的顶点序号由小到大排列，列出从顶点1出发深度优先和广度 优先搜索遍历该图所得顶点序列 和边的序列。1 562 4315 246 3BUPT323.分别画出按以下两种算法求所示无向带权图的最小生成树的过程 1)Prim算法 2)Kruskal算法4.试列出下图中全部可能 的拓扑有序序列，并指 出应用教材182页 算法toposort求得的是哪一个。abcedfgh493265355765451 2 35 6 4BUPT335.对于如下AOE网络，计算各活动弧的e(ai)和l(ai)函数值，列出关键路径。123456789a1=6a2=4a3=5a4

16、=1a5=1a6=2a7=9a8=8a9=4a10=2a11=4BUPT34第九章 查找 基本概念 静态查找表和动态查找表的含义 平均查找长度ASL的定义BUPT35 静态查找表 顺序查找、折半查找、分块查找的算法思想、算法实现、ASL的分析计算 折半查找对存储结构和关键字的要求 三种查找方法的主要优缺点BUPT36 动态查找表 二叉排序树的定义、特点和用途 二叉排序树的查找方法和算法实现、ASL的分析和计算 二叉排序树的插入、删除、建树方法 输入实例对所建二叉排序树形态的影响 平衡二叉树的定义和作用 BUPT37 哈希表 哈希表、哈希函数、哈希地址和装填因子等有关概念 哈希函数的选取原则及产

17、生冲突的原因 常用的哈希函数的构造方法 解决冲突的主要方法 产生“堆积”现象的原因 哈希表查找和其它表查找的本质区别。采用线性探测法或拉链法解决冲突时，哈希表的建表方法、查找过程以及ASL的分析计算 BUPT381.已知含12个关键字的有序表及其相应权值为：1 2 3 4 5 6 7 8 9 10 11 12 关键字 A B C D E F G H I J K L 权值 4 6 3 4 9 3 2 6 1 5 3 4(1)画出对以上有序表进行折半查找的判定树，求折半查找时查找成功的平均查找长度ASL。(2)若为等概率查找，求折半查找时查找成功的平均查找长度ASL。BUPT393.已知如下长度为

18、12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度ASL。BUPT40选取哈希函数H(k)=(3k)MOD 11。1)用线性探测开放定址法处理冲突，2)用链地址法处理冲突 试在010的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表，并求等概率情况下查找成功时的平均查找长度和不成功时的平均查找长度以及装填因子。BUPT41第十章 内部排序 基本概念 排序方法的稳定性

19、的含义 排序算法评价标准BUPT42 插入排序 直接插入排序的基本思想、算法实现、时空性能 希尔排序的基本思想和时空性能 BUPT43 交换排序 冒泡排序的基本思想、算法实现、时空性能 快速排序的基本思想、算法实现、时空性能 枢轴记录的选取对快速排序的影响 针对给定的输入实例，写出快速排序的排序过程 BUPT44 选择排序 简单选择排序的基本思想、算法实现、时空性能 锦标赛排序的基本思想和时空性能 堆的有关概念和定义 堆的性质及堆与完全二叉树的关系 堆排序的基本思想、算法实现、时空性能 针对给定的输入实例，能写出堆排序的排序过程BUPT45 归并排序 两路归并排序的基本思想、算法实现、时空性能

20、 针对给定的输入实例，能写出归并排序的排序过程 BUPT46 基数排序 基数排序的基本思想、时空性能。针对给定的输入实例能写出基数排序的排序过程 基数排序和其它几类排序的本质区别BUPT47 各种排序方法的比较 掌握各种排序的主要特点 根据实际问题的特点和要求选择合适的排序方法BUPT481.以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：(1)直接插入排序 (2)希尔排序(d1=5,d2=3,d3=1)(3)快速排序（第一个记录作为基准记录）(4)堆排序 (5)归并排序 (6)基数排序