2015年考研宝典.docx

中国科学技术大学2015年复试资料3.2复试流程1 .接受咨询;领取材料;签署协议2 .材料审核:按序号分组进行3 .专业面试:专业面试!0-15分钟一位4,英语面试:身份验证后参加英语面试室。英语面试5-8分钟一位5 .综合素质测试和专业测试(C语言和数据结构)特别注意的是调剂的学生,所有参加调剂的考生须上教育部研招网调剂3.3.1数据结构与算法1.时间复杂度按数量级递增排列,常见的时间复杂度有:常数阶0(1),对数阶O(logm),线性阶0(n),线性对数阶0(nlog2n),平方阶0(),立方阶。()，k次方阶0(n*)»指数阶0(2")。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。2.各种排序的时间复杂度和性能比较排序类别基本思路详细分类时间复杂空间复特注意度杂度点插入排序每趟将个待排序的元直接插入(边比较边移最好(正序)：0(n)0(1),需要个监视稳定排直接插入排序所产生的有序区不一定是全局有序的,有序区中素,按其关键字值的大小插入到已经动)最坏(逆序)：0(n2)哨。序的关键字并不一定大于或小于无序区中所有元素的关键字,这样每一趟排序并不一排序的有序区中的适当位置±,直到全部插入完成。平均:0(n2)定将一个元素放置在最终的位置上。插入排序与待排序数据的顺序有关,当正序时效率最高，当反序时效率最低。折半插入(先比较后移动)平均：0(n2)折半插入排序仅减少了关键字间的比较次数，而元素的移动次数不变。希尔排序平均：0(n'1.3)。不稳希尔排序每一趟并不产生有序区,也不定排序定将一个元素放置在最终的位置上,希尔排序和待排序数据的顺序有关,正序时最高,逆序时效率最低。交换排序基本思想:两两比较待排序元素的关键字,发现两个元素的次序相反时即进行交换,直到没有反序的元素为止。每趟排序都将个元素放到最终位置上。冒泡排序最坏:0(n2)平均：0(n2)最好:。稳定排序冒泡排序中所产生的有序区一定是全局有序的,有序区中的所有元素的关键字一定大于或小于无序区中所有元素的关键字，每趟排序都将一个元素放置到最终位置±,起泡排序与待排序数据的顺序有关，正序效率最高，逆序效率最低。快速排序:在待排序的n 个元素中任取个元素(通常取第一个元素)作为基准,把该元素放入最终的位置上(归为个元素),数据序列被此元素划分成两部分：所有关键字比该元素关键最坏:0(n2)平均: O(nlog2n)最好: O(nlog2n)最坏:0(n)平均:0(log2 n)不稳定排序在快速排序算法中,并不产生有序区，但每趟归位个元素,快速排序与待排序数据的顺序有关,当正序和逆序时效率都低,只有当数据随机分布,每次划分的子区间长度大致相等时效率最高。字小的元素放置在前,部分,所有比他大的元素放置在后一部分,这个过程称为趟快速排序,以后对所有的两部分分别重复上述过程,直至每部分内只有一个元素或空为止。选择排序基本思想:每趟从待排序的元素序列中选出关键字最大（或最小）的元素,按顺序放在已排序的元素序列的最后面（或最前面）,直到全部排完为止。选.序选键小素有的形的区的。单叫无中关最元在区局新序新腓简择在区择字的放序最成有和无08。不稳定排序有序区全局有序,有序区中的所有元素关键字要么全部大于无序区,要么全部小于无序区,每趟排序归为个元素,时间复杂度与待排序数据序列的顺序无关。堆排序:种树O(nlog2n)<?(1)不稳建初始堆所需要的比较次数较多,所以堆形选择排序。在排序过程中,将 R1n看成是兀生叉树的顺序存储结构,利用完全叉树中的双亲和孩子结点之间的关系来找到当前序列中关键最大/小的元素。定排序排序不适宜于元素较少的表。所产生的有序区一定全局有序,有序区要么全部大于或小于无序区中的关键字,每趟排序归为个元素,时间复杂度与待排序数据顺序无关。归并2路归O(nlog2n)<?(»)稳归并排序的时间复杂排序并排序:初始序列含有n 个记录,贝可以看成是n 个有序的子序列,每个子序列的长度为1,然后两两归并,得定排序度与初始序列无关唱个长度为2或1的有序子序列;再两两归并,如此重复,直至得到个长度为n的有序序列为止基数排序借助多关键字排序的思想对单逻辑关键字进行排序有两种实现方式:最高位优先(MSD):即先对最高位进行排序,将序列分成若干个子序列,然后就每个子序列按次高位进行排序,再分成若干个更小的子序列,依次重复,最后将所有子序列依次平均和最坏都为O(d(n+ rd )n为序列中的元素数,d为关键字位数为关键字的取值范围。(喲联接在起成为个有序序歹();(2)最低位优先(LSD)：先从最低位开始排序,依次重复,直至对最高位排序后便成为个有序序3 .什么是堆,有什么作用堆是一种数据结构,可以把堆看成一棵完全叉树,这个完全叉树满足:任何个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小,则这样的堆叫做大顶堆;若父亲小孩子大,则这样的堆叫做小顶堆。利用堆这种数据结构的性质,通过堆元素的删除、调整等系列操作将最小(大)数选出放在堆顶,来实现堆排序。4 .时间复杂度为O(nlogzn)的排序方法时间复杂度为O(nlogm)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好。5 .直接插入算法Function Naie： InsertSortDescription:直踊入排序,按聊船排列。,：Parameter： SqList *pSqListGreater： turinghfe®gmail.coiTime：18:242010-7-14jiodify：18：122012-0H6添加注& pElem坏和储有效嬲,任瞰雏翻陶研飢程施辦比牖。需要进行排序的飜从。:4:pElenl开粧儼桜00075:void lnS6rtS0rt ISqList -pSqListj00078:000'9:int i, j;00080:00081:for(i =2; i <= pSqList->iIiength; i-H)00082:/Z待插入的元素償小于己经有锄序列的最后一个值00084:if(pSqList->pElemi< pSqList->pEleni -1)I将i元素放入监视哨住置00087:pSqList->pElem0= pSqList->pElemi;00088:'''/Z从i-1开始,寻找插入烏若大升揃值,则直接将遭插入到揃位置,柿蠣助元素，/Z若小升说值,就需要将大员的值,依次,直到找到插入色亂:：for(j = i -1; pSqList->pElem(0< pSqLiit->pEleaj;j)00092:00093:pSqList->pElemj +1= pSqList->pElemi;00094:00095:二:96:pSqList->pElemj +1= pSqList->pElem0;00097:00098:00099:? end InsertSort ?注:程序中pElem0是哨兵,作用:避免不必要的判断语句,提高效率。6 .折半插入算法Function Name： BlnsertSortDescription:折半插入排序,按照非递减排列。Binary Insert Sort Parameter： SqList *pSqList:Greater： turinglifegmail. comTime 18:482010-7-14;:Modify：19:222012-04-08 pElem被用作监视哨,并不放置待排序数据。31010101010101010fol010101010101010101010101010101010101010101010101c|o|Q|o|o|o|o|o|cfc|o|o|o|o|o|ofo|cfo|o|o|o|o|o|c|o|c|o|o|Q|o|ofc /00147: void BlnsertSort(sqL13t pSqLxst)00148:int i, j, low, high, mid;?2151:for(i =2; i <= pSqList->iLength; i+)00152:00153:pSqList->pElem0= pSqList->pElemi;low =1;00156:high = i -1;/利用折半査找,査找插入点.00159:while(low <= high)00160:00161:mid =(low + high)/2;00163:if(pSqList->pElemmid> pSqList->pElemO)00164:high = mid -1;00165:else00166:low = mid +1;/Z记录后移00170:for (j = i -1; j >=(high +1)；j)00171:pSqList->pElem(j +1= pSqList->pElemj;/Z插入正确位置:pSqList->pElemhigh +1= pSqList->pElemO;0016: end for=pSqLjgc->iLeng00178:return;0 Q j / Q *BI n 3 e 匸 S r 7 .什么叫堆排序?与快速排序有什么不同?答案请参看上表:快速排序1、每趟排序不产生有序区;2、时间复杂度与待排序数据顺序有关;3、空间复杂度与待排序数据顺序有关8 .循环队列的顺序表示中,为什么要空个位置?循环队列那个空位置为了便于辨别对空和队满9 .什么是叉查找树,原理叉排序树(Binai"y Sort Tree)又称叉查找树。它或者是棵空树；或者是具有下列性质的叉树；(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值；(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值；(3)左、右子树也分别为叉排序树；步骤:若根结点的关键字值等于查找的关键字,成功。否则,若小于根结点的关键字值,递归查左子树。若大于根结点的关键字值,递归查右子树。若子树为空,查找不成功。中序遍历叉查找树可得到个关键字的有序序列。10 .排序算法最优的时间复杂度(11,13)基于比较的排序算法中最好时间复杂度为0(nlog2n)o11 .哈夫曼树(11,12,13)给定n个权值作为n个叶子结点,构造棵叉树,若带权路径长度(WPL)达到最小，称这样的叉树为最优叉树，也称为哈夫曼树(Huffman tree)特点:(1)权值越大的结点,距离根结点越近。(2)树中没有度为1的结点。哈夫曼树又称为严格的(正则的)叉树。12.哈夫曼树的应用:哈夫曼编码。任一字符的编码都不是另个字符的编码的前缀,这种编码成为前缀编码。设计棵哈夫曼树,由此得到的二进制编码前缀编码便称为哈夫曼编码。构造方法:假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为wl、w2、wn,则哈夫曼树的构造规则为：(1)将wl、w2、，wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选取的两棵树,并将新树加入森林;(4)重复(2)、(3)步,直到森林中只剩棵树为止,该树即为所求得的哈夫曼树。13 .什么是哈希冲突,及如何解决(13)哈希表:散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。常用散列函数:1、 直接寻址法)=key/f(fcey)= a x ksy + b2、 数字分析法假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字若干数位组成哈希地址。3、 平方取中法取关键字平方后的中间几位为哈希地址,取的位数由表长决定。4、折叠法将关键字分割成位数相同的儿部分(最后一部分位数可以不同),然后取这儿部分的叠加和(舍去进位)作为哈希地址。4、 随机数法H(key)=random(key), random 为随机函数。5、 除留余数法H(key)=key % p, p=m(表长)。处理冲突的方法:6、 开放寻址法:=(H(key)+di)%mi =1,2 k;根据4的取法分1) 线性探测法:¢=1,2，,m-l ；2) 平方探测法:d =F,t2,22,_22,.土2(k<m/2);3) 伪随机序列法：4=伪随机数序列链地址法7、 再哈希法：Hi=RHi(key)i = l,2,.,k ；3、链地址法：将所有关键字为同义词的记录存储在同一线性表中;8、 建立一个公共溢出区散列因子：a =填入表中的元素个数/散列表的长度a是散列表装满程度的标志因子。由于表长是定值,a与“填入表中的元素个数”成正比,所以,a越大,填入表中的元素较多,产生冲突的可能性就越大;a越小,填入表中的元素较少,产生冲突的可能性就越小。14 .深度、广度搜索的过程图的深度优先遍历：假设给定图G的初态是所有顶点均未曾访问过。在G中任选顶点v为初始出发点(源点),则深度优先遍历可定义如下：首先访问出发点V,并将其标记为已访问过;然后选取与v邻接的未被访问的任意个顶点w,并访问它,再以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。图的深度优先遍历耗费的时间取决于所采用的存储结构。当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(+ e)。使用数据结构:堆栈图的广度优先遍历:首先访问起始点v,然后依次访问v的各个未曾访问过的邻接点,再分别从这些邻接点出发依次访问它们的邻接点(已经访问过的除外)，并且要使得“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点“被访问，直至图中所有已被访问的顶点的邻接点都被访问到。图的广度优先遍历类似于树的层次遍历。采用的搜索方法的特点是尽可能先对广度方向进行搜索。这种搜索方法称为广度优先搜索(Breadth-First Search)相应地,用此方法遍历图就很自然地称之为图的广度优先遍历。图的广度优先搜索遍历图的时间复杂图和深度优先搜索遍历相同。使用数据结构:队列15 .图的深度优先遍历序列是否唯一?为什么?不一定唯一。当从某顶点x出发搜索时,若x的邻接点有多个顶点尚未访问过，则我们可任选个访问之。16 .迪杰斯特拉算法的过程Dijkstra (迪杰斯特拉)算法是典型的单源最短路径算法,用于计算个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra 一般的表述通常有两种方式,一种用永久和临时标号方式,种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。算法步骤如下:1 .初使时令S=V0,T=其余顶点, T中顶点对应的距离值若存在<V0,Vi>, d(V0,Vi)为V0,Vi>弧上的权值若不存在V0,Vi>, d(V0,Vi)为OC2 .从T中选取个其距离值为最小的顶点W且不在S中，加入S3 .对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,则修改此距离值重复上述步骤2、3,直到 S中包含所有顶点,即S=T为止17 .链表查询某个元素,平均时间复杂度是多少?。()18 .链表可以用什么实现,循环链表的实现方式?如何快速找到位于单链表中间的节点?链表可由指针和数组来实现。循环链表:将单链表的最后一个结点的NULL指针改为指向开始结点即可。设置两个指针 fast、slow都指向单链表的头节点。其中 fast的移动速度是 slow的2倍。当 fast指向末尾节点的时候，slow正好就在中间了。19.图的存储方式邻接矩阵用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。在用邻接矩阵存储图时,除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用个维数组来存储顶点信息,另外还有图的顶点数和边数。图的邻接矩阵表示是唯的,且无向图的邻接矩阵一定是个对称矩阵。从图的邻接矩阵存储方法容易看出这种表示具有以下特点:无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。对于无向图,邻接矩阵的第i行（或第i歹）非零元素（或非8元素）的个数正好是第i个顶点的度TD（vi）o对于有向图,邻接矩阵的第i行（或第i歹）非零元素（或非8元素）的个数正好是第i个顶点的出度OD（vi）（或入度ID（vi）。用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连;但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。邻接表是图的链式存储结构。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi,将所有邻接于vi的顶点vj链成一个单链表,这个单链表就称为顶点vi的邻接表,再将所有点的邻接表表头放到数组中,就构成了图的邻接表。vertex若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然,在边稀疏（en（nT）/2）的情况下，用邻接表表示图比邻接矩阵节省存储空间,当和边相关的信息较多时更是如此。在无向图的邻接表中,顶点vi的度恰为第i个链表中的结点数;而在有向图中,第i个链表中的结点个数只是顶点vi的出度,为求入度,必须遍历整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。十字链表有向图的另种链式存储结构,它实际上是邻接表与逆邻接表的结合，即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。邻接多重表无向图的链式存储结构20.图相关概念有向图无向图弧,弧头,弧尾边有向完全图:n*(nT)条弧的有向图完全图:l/2*n*(n-l)条边的无向图稀疏图:很少条边或弧(如enlogn)的图稠密图:e>nlogn权:有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权网:带权图称为网子图:假设有两个图G=(V,E)和G'=(,E'),如果V是V的子集, E是E的子集,则称G为G的子图。邻接点:对于无向图G=(V,E),如果(v,v')eE»则顶点v与V，互为邻接点路径:顶点序列,路径的长度就是路径上的边或弧的数目。回路/环：第一个顶点和最后个顶点相同的路径称为回路/环简单路径：序列中顶点不重复出现的路径称为简单路径简单回路/简单环：除了第一个顶点和最后个顶点之外,其余顶点不重复出现的冋路，称为简单冋路/简单环出度:以顶点v为尾的弧的数目 入度：以顶点V为头的弧的数目强连通图：有向图中任意两个不同顶点 A、B.从顶点A到顶点B和从顶点B到 顶点A都存在路径，则称为强连通图。 强连通分量：有向图中的极大强连通子 图生成森林:个有向图的生成森林由若 千棵有向树组成,含有图中全部顶点, 但只有足以构成若干棵不相交的有向 树的弧。有向树：如果个有向图恰好有二个顶 点的入度为0,其余顶点的入度均为1, 则是棵有向树。度:和顶点v相关联的边的数目连通：无向图中从顶点A到顶点B有 路径,则称两个顶点连通。连通图：图中任意两个顶点都是连通 的，则称为连通图。连通分量:无向图中的极大连通子图生成树：极小连通子图,含有图中全部 顶点,但只有足以构成一棵树的(nT) 条边。如果在一棵生成树上添加一条 边，必定构成一个环。21.连通图的概念在图论中,连通图基于连通的概念。在个无向图G中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果G是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。图的连通性是图的基本性质。22.什么图可以进行拓扑排序拓扑排序,是指将一个有向无环图中所有顶点排成一个线性序列,使得图中任意对顶点u和v,若GE(G),则u在线性序列中出现在v之前的排列方式。有向无环图，可进行拓扑排序,结果般不唯一。当有向图存在环时,不能进行拓排。23. 非连通图如何遍历访问每个节点可对非连通图进行深度优先遍历。24. 图的两种存储方式(顺序表矩阵和链表),各适用什么图顺序表矩阵适用稀疏图,链表适用稠密图。25. 解释下最小生成树带权连通无向图G的所有生成树集合中,边的权值最小的那棵生成树。即极小连通子图，含有图中全部顶点,但只有足以构成一棵树的(n-l)条边。如果在棵生成树上添加一条边,必定构成一个环。26. n个节点的图的最小生成树有几个节点,几条边n个顶点,n-l条边。27. 平衡叉树平衡叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法)，且具有以下性质:它是棵空树或它的左右两个子树的高度差的绝对值不超过1(-1,0,1)«并且左右两个子树都是一棵平衡叉树。AVL树是最先发明的自平衡叉查找树。AVL树得名于它的发明者G. M. Adelson-Velsky 和 E. M. Landis,他们在1962年的论文”An algorithm for the organization of information/Z 中友表了它。查找、插入和删除在平均和最坏情况下都是(logn)。增加和删除可能需要通过,一次或多次树旋转来重新平衡这个树。28. 叉树怎么存储1、顺序存储结构:用组地址连续的存储单元依次自上而下、自左向右存储完全叉树上的结点信息。这种顺序存储结构仅适用于完全叉树。否则其他形式的叉树用顺序存储,会浪费不少存储空间。2、链式存储结构:叉链表、三叉链表。含有n个结点的叉链表中有n+1个空链域。29. 单链表就地逆置所谓“就地”是指算法的辅助空间为0(1)思路：用指针p扫描原单链表,先将头节点L的next域设置为NULL而变成一个空链表,然后将p节点采用头插法插入到L中。算法:Function Name： reverseDescription：单涟表就地逆普算法,采用头插法重建单道表。所谓"就地”是指算法的辅助空间为o（）Parameter ：Greater： turinglife Time 14:362010-4-14:reverse（i,：nks ）（ 一 LxnkLxst *p = L>nex , *q;L>next = NUItli；Modify：30. 査找方法总结动态査找表:若在查找的同时还对表做修改运算（如插入或删除）,则相应的表称之为动态査找表。静态查找表:反之称为静态查找表。查找类型平均查找长度时间复杂度适用存储结构原理顺序查找（静态查找）成功:(n+l)/2失败:n0(n)线性表的顺序存储和链式存储都可以从表的一端开始，顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到记录的关键字与k相等,则查找成功;若扫描结束后,仍未找到关键字等于k的记录,则查找失败。折半查找（静态查找）成功：查找过程恰好走了一条从判定树的根到被查记录的路径,经历比较的关键字次数恰为该记录在树中的层次。在最坏的情况下查找成功和查找不成功的比较次数均不超过判定树的高度，即 log2（n+1）顺序存储结构且要求元素按关键字有序排列首先用要查找的关键字k与中间位置的节点的关键字相比较,这个中间记录把线性表分成了两个子表，若比较结果相等则查找成功;若不相等，再根据k与该中间记录关键字的比较大小确定下步查找哪个子表,这样递归进行下去。注意:折半查找的过程可用叉树来描述,把当前查找区的中间位置上得记录作为根,左子表和右子表中的记录作为根的左子树和右子树，由此得到的叉树称为描述折半查找的判定树或比较树失败:比较过程经理了一条从判定树根到某个外部节点的路径,所需关键字比较次数不超过判定树的高度。0(log2n)B树=多路平衡查找树（动态查找）特点:1、所有叶子节应该同二叉查找树0（log2n）查找过程：B树查找过程类似于叉查找树上的查找过程，不同的是在每个记录确点都在同一层,且不带任何信息。2、若根节点不是终端节点,则根节点至少有两棵子树。3、树中每个节点至多有m 棵树4、所有内部每个节点至少口m/2口棵子树。定向下査找的路径不定是二路的。因为个节点内的关键字有序,故节点内可以采用顺序查找或折半査找。stepl:找结点 step2：结点内找关键字插入过程:插入过程分两步,定位和插入。定位过程利用上面的查找算法,插入过程分为不分裂和分裂两种情况。分裂插入有可能导致B树增高层。删除过程:两大类。第一类在非最底层的非叶子节点上删除关键字。第二类在最底层非叶子节点删除关键字,这类型又分三种情况。情况,直接删除关键字,情况二,兄弟够借,情况三,兄弟不够借(合并),情况三有可能导致B树减少层。B+树如果是从根节点开始进行随机查找的话,应该同叉查找树 O(log2n)查找过程：两种查找方法，第一种，直接从最小关键字开始进行顺序查找。第二种,从B+树的根节点开始进行随机查找。插入过程：仅在叶子节点中插入关键字删除过程：仅在叶子节点中删除关键字31. 叉查找树和数组实现的二分查找的区别叉查找树实现的二分查找:当叉查找树不空时,首先将给定值和根结点的关键字比较,若相等,则查找成功,否则将依据给定值和根结点的关键字之间的大小关系,分别在左子树和右子树上继续进行查找。数组实现的二分查找:首先用要查找的关键字k与中间位置的节点的关键字相比较,这个中间记录把线性表分成了两个子表,若比较结果相等则查找成功;若不相等,再根据k与该中间记录关键字的比较大小确定下步查找哪个子表,这样递归进行下去。32. m阶的B树和m阶的B+树主要区别1、B+树所有有效数据全在叶子节点,而B树所有有效数据分散在树非叶子节点中,B树中的关键字不重复。2、B+树种有几个关键字就有几个子树,B树中具有n个关键字的节点含有(n+1)棵子树。3、B+树有两个指针,根指针和指向最小节点的指针,叶子节点连接成一个不定长的线性链表4、B+树中，每个节点(除根节点外)中的关键字个数n的取值范围是口m/2口=n=m,根节点n的取值范围是2<=n<=mo B树中,每个节点(除根节点外的所有非叶子节点)中的关键字取值范围是 m/2-1<=n<=m-1,根节点n的取值范围是K=n<=m-lo5、B+树中的所有非叶子节点仅仅起到索引的作用,节点中的每个索引项只包含对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。而在B树中,每个关键字对应记录的存储地址。33. 折半查找，适用范围和时间复杂度适用范围:顺序存储结构且要求元素按关键字有序排列时间复杂度:O(log?n)34. 栈和队列的区别(1)队列先进先出,栈先进后出。(2)对插入和删除操作的限定"。栈是限定只能在表的一端进行插入和删除操作的线性表。队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。(3)遍历数据速度不同。栈只能从头部取数据也就最先放入的需要遍历整个栈最后才能取出来,而且在遍历数据的时候还得为数据开辟临时空间,保持数据在遍历前的一致性。队列则不同,它基于地址指针进行遍历,而且可以从头或尾部开始遍历，但不能同时遍历,无需开辟临时空间。35. 满叉树的结点个数(n层)2”-1个36. 树与叉树的区别,什么是完全叉树树是若干个结点的集合,是由唯一的根和若干棵互不相交的子树组成的。其中每一棵子树又是棵树,也是由唯一的根和若干棵互不相交的子树组成。树的结点数目可以为零,此时它就是棵空树。叉树:(1)每个结点最多只有两棵子树,即叉树中结点的度只能为0,1,2。(2)子树有左右之分,不能颠倒。满叉树:在一棵叉树中,如果所有的分支结点都有左孩子和右孩子结点,并且叶子结点都集中在叉树的最下层,这样的叉树称为满二叉树。完全叉树:如果棵深度为k有n个结点的叉树,进行编号后,若结点的编号与深度为k的满叉树中相同位置上的结点的编号均相同,则这棵叉树就是完全叉树。37. 什么是队列,顺序队列的特征队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。顺序队列是存储在地址连续的存储空间中,顺序队会出现“假溢出”,可以使用循环队列来解决。循环队列会空出个位置,便于判断队空和队满。循环队列在实现时,rear和front指针不是沿着数组下标递增地直线行走,而是沿着个环走,走到数组尽头的时候自动返回数组起始位置。front=(front+l)%maxSize (maxSizes 是数组长度),rear 类似。38. 有哪些方法可以实现队列(追问:既然队列可以用顺序存储实现,并且顺序存储是随机访问的,那为什么还要限制队列只能头尾操作? Tips:减少成本)链式存储,顺序存储均可以实现队列。39. 叉树的层次遍历要进行层次遍历,需要建立一个循环队列先将叉树头结点入队列,然后出队列,访问该结点,如果它有左子树,则将左子树根结点入队列;如果它有右子树,则将右子树根结点入队列。然后出队列,对出队结点访问,如此反复,直到队列为空为止。40. 层次遍历算法41. void LevelOrder(BTNode *b)42. (43. BTNode *p;44. BTNode #quMaxSize;45. int front,rear;46. front=rear=-l;47. reari;48. qurear=b;49. while(front!=rear)50. 51. front=(front+l)%MaxSize;52. p=qufront;53. printf(M%c Hjp->data);54.55. if(p->lchild!=NULL)56. j(57. rear=(rear+l)%MaxSize;58. qurearsp->ichild;59. 60.61. if(p->rchild!=MULL)62. (63. rears(rear+l)%MaxSize;64. qurearsp->rchild;65. I)66. )67. J )数据结构与算法重点补充排序算法总结(1)排序稳定性:快速排序,希尔排序,简单选择排序,堆排序是不稳定排序,其他都是稳定排序(2)经过趟排序,能够保证个元素到达最终位置,这样的排序是交换类排序的那两种(冒泡,快速)和选择类的那两种(简单选择,堆)(3)排序方法的元素比较次数和原始序列无关简单选择排序和折半插入排序(4)排序方法的排序趟数和原始序列有关交换类排序(5)比较直接插入排序和折半插入排序二者最大的区别在于寻找插入位置的方式不同。直接插入是按顺序查找的方式,而折半插入按折半查找的方式。顺序表和链表比较(1)基于空间的比较存储分配方式:顺序表的存储空间是静态分配的,链表则是动态分配的;存储密度(结点值域所占存储量/结点结构所占存储量)顺序表=1;链表1(因为结点中有指针域)。(2)基于时间的比较存取方式:顺序表可以随机存取,也可顺序存取;链表只能顺序存取。插入/删除时移动元素个数:顺序表平均需要移动近一半元素,对顺序表进行插入和删除的平均时间复杂度为0();链表只需修改指针,不需要移动元素。字符串模式匹配算法简单模式匹配算法时间复杂度O(nXm), n为主串规模,m为模式串规模算法思想:从主串的第一个位置起和模式串的第一个字符开始比较,若相等,则继续比较后续字符;否则从主串的下个字符开始与模式串的第一个字符比较，依次类推,直到比较完模式串的全部字符。若模式串中的每一个字符都和主串中的一个连续的字符序列相等,则称为匹配成功;反之则匹配不成功。KMP算法时间复杂度O(n+m)。改进在于:每当一趟匹配过程中出现字符比较不等时，不需要回溯比较指针,而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的距离后，继续进行比较。KMP算法改进最需要解决的问题是,当匹配过程中产生“失配”时,模式串“向右滑动”可行的距离多远。在匹配过程中,主串中第j个字符与模式中第i个字符比较不等时,仅需要将模式向右滑动至模式中第k个字符和主串中第j个字符对齐,此时,模式中头 k-1个字符的子串必定与主串中第j个字符之前的长度为k-1的子串相等,由此,匹配仅需要从模式中第k个字符与主串中第j个字符处开始比较。首先需要计算出个next数组,next i代