C题库期末复习.pptx

BUPT期末复习BUPT1第一章绪论数据结构的基本概念和术语数据、数据元素、数据项、数据对象、数据结构等基本概念数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系数据结构的四种逻辑结构及四种常用的存储表示方法抽象数据类型的概念及其与数据结构的关系BUPT2算法的描述和分析算法、算法的时间复杂度和空间复杂度的概念算法描述和算法分析的方法BUPT3第二章线性表线性表的逻辑结构线性表的逻辑结构特征线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算BUPT4线性表的顺序存储结构顺序表的存储方式及它如何映射线性表中元素之间的逻辑关系顺序表的存储结构定义线性表基本运算在顺序表上的实现方法及其时间性能分析利用顺序表设计算法解决应用问题BUPT5设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解题思路：在递增有序的顺序表中插入一个元素解题思路：在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素，首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法比顺序查找效率要高。递增有序，采用折半查找法比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素后移动一个元素位置，之后将元素x插入即可。假插入即可。假设顺序表设顺序表va存放在数组存放在数组A中（假设下标从中（假设下标从1开始）。开始）。voidInsert（ElemTypeA，int size,ElemTypex）。low=1；high=num；/假设下标从1开始while（lowx）high=mid-1；elselow=mid+1；for（i=num；i=low；i-）Ai+1=Ai；元素后移。Ai+1=x；将元素x插入。算法结束BUPT6线性表的链式存储结构链表的存储方式及它如何映射线性表中元素之间的逻辑关系链表中头指针和头节点的使用单链表、双链表、循环链表在链接方式上的区别各种链表的存储结构定义线性表基本运算在链表上的实现方法及其时间性能分析循环链表上尾指针取代头指针的作用利用链表设计算法解决简单的应用问题BUPT7已知线性表中的元素以值递增有序排列，并以单链表（带头结点）作为存储结构，试写一算法删除表中所有值大于mink且小于maxk的元素。解题思路：首先找到最后一个元素值小于等于解题思路：首先找到最后一个元素值小于等于mink的结点的结点位置（位置（q）；再往后依次删除结点直到第一个值大于等于）；再往后依次删除结点直到第一个值大于等于maxk结点为止。结点为止。voiddelete(sqlist*la,intmink,intmark)sqlist*p,*q,;q=la;p=la-next;while(p&p-datanext;while(p&p-datanext;free(p);q-next=p;BUPT8写出单链表（带头结点）就地逆置算法。voidreverse(linklist*h)linklistp,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第三章栈与队列栈的逻辑结构，存储结构及其相关算法栈的逻辑结构特点，栈与线性表的关系顺序栈和链栈的存储结构定义顺序栈和链栈上进栈、退栈等基本运算的实现方法栈上的“上溢”和“下溢”的概念及其判别条件递归过程中栈的作用设计递归程序的原则和方法利用栈设计算法解决简单的应用问题BUPT11假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，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=rear-next;/将s结点链入队尾rear-next=s;rear=s;/rear指向新队尾voidDeQueue(LinkedListrear)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串的存储结构和基本运算的实现串的两种主要存储结构顺序串和链串的存储结构定义（C语言的类型描述）顺序串上串的基本运算的实现朴素的模式匹配算法与朴素的模式匹配算法与KMP算法的算法思想及算法的算法思想及时间复杂度分析时间复杂度分析KMP算法中算法中next和和nextval数组的求值方法数组的求值方法BUPT17求模式串t1=aaab，t2=abcabaa，t3=adabbadada的next和nextval数组值BUPT18第六章树树的概念树的逻辑结构特征树的常用术语及含义BUPT19二叉树二叉树的定义，二叉树与树的差别完全二叉树和满二叉树的概念二叉树的性质二叉树的顺序存储结构和链式存储结构的定义（C语言的类型描述）和表示方法BUPT20二叉树的遍历二叉树的先序、中序、后序、层序遍历算法求给定二叉树的先序、中序、后序遍历对应的结点访问序列由二叉树的先序和中序、中序和后序、中序和层序的序列确定二叉树以遍历算法为基础，设计有关算法解决简单的应用问题BUPT21线索二叉树二叉树线索化的目的线索二叉树存储结构的表示方法在线索二叉树中查找给定结点的前趋和后继的方法BUPT22树和森林树和森林与二叉树之间的转换方法和对应关系树的各种存储结构的表示方法及其特点树的先序和后序遍历方法森林的先序和中序遍历方法BUPT23哈夫曼树及其应用最优二叉树的概念及特点求哈夫曼树的方法设计哈夫曼编码的方法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）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回TRUE，否则返回FALSE（假定被判定的操作序列已存入一维数组A中）。BUPT25三、设模式串t=abcabaa，试求出该模式串的next和nextval数组的值。四、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）。BUPT26第七章图图的概念图的逻辑结构特征图的常用术语及含义图的存储结构图的邻接矩阵的存储结构定义及表示法和特点图的邻接表的存储结构定义及表示法和特点BUPT27图的遍历图的深度优先搜索和广度优先搜索遍历算法及时间性能确定两种遍历所得到的顶点访问序列图的两种遍历与树的遍历之间的关系利用图的两种遍历设计算法解决简单的应用问题BUPT28生成树和最小生成树生成树和最小生成树的概念对给定的图画出深度和广度优先生成树或生成森林Prim和Kruskal算法的基本思想对给定的连通图，根据Prim和Kruskal算法构造出最小生成树BUPT29有向无环图的应用拓扑排序的基本思想和步骤拓扑排序不成功的原因求给定AOV网的拓扑序列关键路径、关键活动的概念求AOE网的关键路径的步骤和方法对给定的AOE网，求关键路径和工期BUPT30最短路径最短路径的含义求单源最短路径的Dijkstra算法的基本思想和时间性能对于给定的有向图，画出根据Dijkstra算法求单源最路径的过程示意图求每一对顶点间最短路径的Floyd算法的基本思想和时间性能A(k)i,j(1kn)的含义对于给定的有向图，用Floyd算法求每一对顶点之间的最短路径长度，能写出A(0)，(1)，(n)的值BUPT311.请给出所示有向图的1)每个顶点的入/出度；2)邻接矩阵；3)逆邻接表；4)强连通分量。2.画出所示无向图的邻接表，它所邻接到的顶点序号由小到大排列，列出从顶点1出发深度优先和广度优先搜索遍历该图所得顶点序列和边的序列。156243152463BUPT323.分别画出按以下两种算法求所示无向带权图的最小生成树的过程1)Prim算法2)Kruskal算法4.试列出下图中全部可能的拓扑有序序列，并指出应用教材182页算法toposort求得的是哪一个。abcedfgh49326535576545123564BUPT335.对于如下AOE网络，计算各活动弧的e(ai)和l(ai)函数值，列出关键路径。123456789a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=8a9=4a10=2a11=4BUPT34第九章查找基本概念静态查找表和动态查找表的含义平均查找长度ASL的定义BUPT35静态查找表顺序查找、折半查找、分块查找的算法思想、算法实现、ASL的分析计算折半查找对存储结构和关键字的要求三种查找方法的主要优缺点BUPT36动态查找表二叉排序树的定义、特点和用途二叉排序树的查找方法和算法实现、ASL的分析和计算二叉排序树的插入、删除、建树方法输入实例对所建二叉排序树形态的影响平衡二叉树的定义和作用BUPT37哈希表哈希表、哈希函数、哈希地址和装填因子等有关概念哈希函数的选取原则及产生冲突的原因常用的哈希函数的构造方法解决冲突的主要方法产生“堆积”现象的原因哈希表查找和其它表查找的本质区别。采用线性探测法或拉链法解决冲突时，哈希表的建表方法、查找过程以及ASL的分析计算BUPT381.已知含12个关键字的有序表及其相应权值为：123456789101112关键字ABCDEFGHIJKL权值463493261534(1)画出对以上有序表进行折半查找的判定树，求折半查找时查找成功的平均查找长度ASL。(2)若为等概率查找，求折半查找时查找成功的平均查找长度ASL。BUPT393.已知如下长度为12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度ASL。BUPT40选取哈希函数H(k)=(3k)MOD11。1)用线性探测开放定址法处理冲突，2)用链地址法处理冲突试在010的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表，并求等概率情况下查找成功时的平均查找长度和不成功时的平均查找长度以及装填因子。BUPT41第十章内部排序基本概念排序方法的稳定性的含义排序算法评价标准BUPT42插入排序直接插入排序的基本思想、算法实现、时空性能希尔排序的基本思想和时空性能BUPT43交换排序冒泡排序的基本思想、算法实现、时空性能快速排序的基本思想、算法实现、时空性能枢轴记录的选取对快速排序的影响针对给定的输入实例，写出快速排序的排序过程BUPT44选择排序简单选择排序的基本思想、算法实现、时空性能锦标赛排序的基本思想和时空性能堆的有关概念和定义堆的性质及堆与完全二叉树的关系堆排序的基本思想、算法实现、时空性能针对给定的输入实例，能写出堆排序的排序过程BUPT45归并排序两路归并排序的基本思想、算法实现、时空性能针对给定的输入实例，能写出归并排序的排序过程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)基数排序