算法题库.doc

第一章和第三章题库Pascal语言的创始人N.Wirth提出的一个著名公式是：程序_+_。算法，数据结构算法的非形式化定义为，它是一个_。有穷的运算规则序列算法的五个特征是：_、_、_、_、_。确定性，能行性，有穷性，有0个或1个以上的输入，有1个以上的输出问题的可计算程度分为三种：_、_、_。算法不可解，算法可解，实际可解分析算法的五个准则是：_、_、_、_、_。正确性，工作量，空间量，简单性，最优性算法的最坏性态是指_。算法所执行的基本运算的最大次数算法的平均性态是指_。 算法在各种输入情况下所执行的基本运算次数的加权平均在分析算法的工作量时，使用的衡量标准是_。基本操作在分析算法的工作量时，一般从_和_两个方面分析。最坏情况、平均情况10.在一个10元素的有序表中查找某数x（x不一定在表中），最坏情况下至少需要比较_4_次。平衡二叉树是树中叶子深度满足_的二叉树。叶子深度之差不超过1epl为二叉树中所有叶子的深度之和，ipl为二叉树中所有内结点（内结点个数为n）的深度之和，则epl和ipl满足_关系。epl=ipl+2n使用淘汰赛法，寻找表中的最大和次大项，最坏情况下需要_次比较操作。使用淘汰赛法，寻找表中的最大和最小项，最坏情况下需要_次比较操作。在n个数的表中寻找最大项，最少需要n-1_次比较。比较函数f(n)=2n3+3n和g(n)=100n2+2n+100的阶，满足_关系。F(n)= (g(n)比较函数f(n)=50nlogn和g(n)=10n+loglogn的阶，满足_关系。F(n)=(g(n)比较函数f(n)=logn和g(n)=(logn)2的阶，满足_关系。F(n)=O(g(n)1算法语言和程序有什么区别？程序算法数据结构，程序设计是算法的实现，是将一个算法的相当详细的描述和它所使用的数据结构变成某一台计算机的程序。二者的区别是：算法语言是算法的描述语言，面向用户，可以用图表、流程图、伪代码等各种形式描述；而程序是在计算机上可以执行的，面向计算机，只能由程序设计语言实现。而且，算法具有有穷性，而程序没有。分析算法的主要目的有哪些？就算法本身而言，可以确定算法的优劣程度，进而选择、修改、构造算法；就算法所解决的问题而言，确定问题实例的可计算程度。2在通常情况下，对算法进行时间复杂度分析时，其基本步骤有哪些？分析算法工作量的步骤有：（1） 确定算法的基本操作（2） 对算法的输入进行分类，并确定每种输入出现的概率（3） 判定每种输入，算法所执行的基本操作次数（4） 按定义式求出算法的时间复杂性3算法的时间复杂度是如何定义的？算法的时间复杂度是算法所执行的基本操作的次数，有平均情况时间复杂度和最坏情况时间复杂度两种提法。4称“解问题P的算法A，在最坏情况下是最优的。”这句话的含义是什么？在解问题P的、和算法A属于同一算法类的任何算法，在最坏情况下所花费的工作量都不比算法A所花费的工作量少。5证明“解问题P的算法A，在最坏情况下是最优的”，主要做哪些工作？（1）求出算法A在最坏的情况下的复杂度W(n)。（2）给出并证明算法所在的算法类中的任何一个算法，解决问题P时，在最坏的情况下至少要执行的基本操作次数F(n)。（3）比较W(n)和F(n)，若W(n)F(n)(或仅相差一个常数倍)就称A是最优的。6假设某算法的时间复杂性为T(n)=2n，在计算机C1和C2上运行这个算法，C2的速度是C1的100倍。若该算法在C1上运行的时间为t，可处理的问题规模为n，在C2上运行同样的时间可处理的问题规模是多少？如果T(n)=n2，在C2上运行同样的时间可处理的问题规模是多少？可以建立公式，T(n)= C1*t,C2=C1*100，所以T(x)=C2*t= 100*C1*t=100*2n,所以在C2上运行同样的时间可处理的问题规模是x=n+log100。按同样的方法，如果T(n)=n2，在C2上运行同样的时间可处理的问题规模是10n。7函数f(n)logn2，g(n)=logn+5，满足f(n)=O(g(n)、f(n)= (g(n)、f(n)=(g(n)中的哪种关系？并加以证明。因为 f(n)= logn2 =2logn ，g(n)=logn+52，所以f(n)= (g(n)。8函数f(n)10，g(n)=log10，满足f(n)=O(g(n)、f(n)= (g(n)、f(n)=(g(n)中的哪种关系？并加以证明。 c（c>0）,所以f(n)= (g(n)。9函数f(n)logn2，g(n)= ，满足f(n)=O(g(n)、f(n)= (g(n)、f(n)=(g(n)中的哪种关系？并加以证明。0，所以f(n)= O(g(n)。10函数f(n)100n2，g(n)=2n，满足f(n)=O(g(n)、f(n)= (g(n)、f(n)=(g(n)中的哪种关系？并加以证明。f(n)= 100n2 =(n2) ，所以n2 和g(n)的关系等同于f(n)和g(n)的关系。取c=1，n0=4，当n>n0时，有n2<=g(n)成立，所以n2O(g(n)，所以f(n)=O(g(n)。11分治法的思想是什么？请举出两个应用分治法思想的算法。分治法是分而治之的方法，它把一个大问题划分为若干规模较小的原问题的子问题；先求其各个子问题的解，可以通过直接求解或再递归分割成若干规模更小的问题直到规模小到可以直接解出为止；然后把各个子问题的解返回得到整个问题的解。二分搜索法、快速整序法使用的就是分治法。12给出求最大最小项的递归算法。求最大最小项的递归算法MAXMIN(L,max,min)1. 算法输入：表L2. 算法输出：max，min3. if |L|=1 then do4. maxL中唯一的元；5. minmax；end；else do6. 把L分解成两部分L1和L2；7. MAXMIN(L1,max1,min1)；8. MAXMIN(L2,max2,min2)；9. maxmax(max1,max2)；10. minmin(min1,min2)；end；13给出二分搜索算法的算法思想和算法描述，并给出w(n)的分析过程。二分搜索算法的思想是：首先将 X 与表的中间项进行比较，如果X 较大，它就可能在后半部分，这样，搜索范围减少了一半。反之，若X 小于表的中间项，则表的后半部分可以不加考虑。若X 等于中间的项，则算法返回。将X 与表中所考虑的部分的中间项继续进行比较，直到找到了X 或者确定X 不在表中时为止。14算法描述 二分搜索（Binary Search）算法输入：L,n0，和X，这里L是一个有 n 项的数组，而 X 是被搜索的项。算法输出：若 X 在L之中，则输出j使满足L(j)=X，若 X 不在L之中，则输出j=0。1. K1；Mn；2. while KM do3. j:=；4. if x=Lj then return j；5. if x<Lj then M:=j-1；6. else K:=j+1；end；7. return 0； (1) 最坏情况分析建立递推方程求解。将上述递推方程进一步展开，得：令又因为k为正整数，所以大于的最小正整数。所以有。15已知：a0, b>0, a、b皆为正整数，有如下算法：输入：a , b输出：Z（Z为何值，自己判断）1. x := a ; y := b; Z := 0;2. while y0 do3. if y为奇数 then do4. Z := Z + x ; y := y1 end;5. x := 2*x ; y := end;6. output(Z)要求：以乘除法运算为基本操作，给出该算法最坏情况下时间复杂度的分析过程。方法一：1，算法的执行时间依赖y的值，y的初值为b2，算法的第2行每通过一次，y的值改变一次 若y为奇数，y的值改为 ： 若y为偶数，y的值也改为：3，该算法的第二行最多通过K次，则y的值最多改变K次，y的值改变K次后有：y=4，算法中止的条件是y=0，即即算法的第35行最多执行次5，算法第5行每执行一次，算法做1次乘法和1次除法。故：方法二：建立并求解递推式16设有三个整数a,b,c,问如何找出它们三者中的中间一个值？你的算法就比较次数来说是最优的吗？该问题的平均复杂度和最坏情况复杂度（按比较次数为基本操作）是多少？算法输入：整数a,b,c（假定三个整数互不相等）算法输出：a,b,c三者的中间值算法过程：1）Avg(a+b+c)/32）a1|a-Avg|,b1|b-Avg|,c1|c-Avg|3）if a1<b1 thenif c1<a1 then output(c);else output(a);elseif c1<b1 then output(c);else output(b);该算法的平均比较次数和最坏情况下的比较次数都是2次（A(3)=2,W(3)=2），而且作为算法中通过求解最小值来求中间值，比较次数无论最坏还是平均情况都需要两次,因而是比较类算法中的最优算法。17假设L是含有n个不同键值的数组，x为指定项，判断x是否在L中出现的算法如下：输入：L , n , x输出：j (j=0时，表示L中无x ; j0时，表示Lj=x)1.j : =n；2.while j0 and Ljx do j : =j1 end；3.Output (j)要求：仅以“x与键比较”为基本操作，（1） 说明该算法的最坏情况输入（2） 若x不在L中出现的概率为1/2 ；x在L中任一位置出现的可能性相同，给出该算法的平均性态A(n)的分析过程（3） 画出该算法的二叉判定树。（1）x在 L1出现或x不在L中出现的输入为最坏输入（2）分析：I. x在L中的输入有n种，令Ii：为Lix的输入，1.对于Ii，算法执行n+1-i次比较后终止，P(Ii)=II. x不在L中的输入有1种。对这种输入，算法执行n次比较后终止，它出现的的概率为，故（3）其判定树为18在BINSEARCH算法中，如果预先知道。则算法及判定树应作如何修改？它的最坏情况及平均性态怎样？输入：具有n个元素的有序表L，x是待搜索的元。输出：输出整数j，代表x在L中相应元的下标。算法过程：1）k:=1;m:=n;2）while k<m do begin3） j:=INT(k+m)/2);4） if x<=Lj then m:=j-1;5） if x>=Lj then k:=j+1;6）end;7）j:=(k+m)/28）output(j)算法的判定树则是将原BISEARCH算法判定树上的叶子结点全部去掉。l 对于最坏情况：由于原BISEARCH算法判定树的高度为，则本题中算法判定树的高度为，所以其最坏情况下的时间复杂度为。l 对于平均性态：由题意可知，本算法输入的情况只有n种，假定每一种输入情况都是等概率发生,那么显然。由于本算法的判定树与书中原BISEARCH算法的判定树相比，去掉了原BISEARCH算法的判定树中全部叶子结点，叶子结点只可能出现在判定数的最后两层上。假定判定数倒数第2层（即层）的叶子结点数为C，并且除最后一层外，判定数的剩余部分为一棵满二叉树。于是得一般情况下：比较次数为1次的输入类 种比较次数为2次的输入类种 比较次数为次的输入类种比较次数为次的输入类种所以该算法的平均复杂度A(n)为对任意整数n，m，计算1)当n,m都为偶数时，原式=2)当n,m都为奇数时，原式=3)当n,m为一奇一偶时，原式=对任意整数n，m，计算1)当n,m都为偶数时，原式=2)当n,m都为奇数时，原式=3)当n,m为一奇一偶时，原式=19求解递推方程20求解递推方程由于，所以。21求解递推方程22求解递推方程 23求解递推方程24求解递推方程25证明对任意正整数n，满足对于任意一个正整数n，总可以找到一个非负整数k（），使得。由于log函数为一个单调递增的函数，所以有：。因此，。26证明对应任意整数n0，a、b>0，有假设，其中,a ,b , d 均为整数 , d < ab ;则有所以：27证明对应任意整数a、b>0，有假设： 其中n , m均为整数 ，且 m<b；则：28证明29。证明具有n个内点的平衡二叉树的高（最大深度）。具有n个内点的平衡二叉树有n+1片叶子，平衡二叉树第d层上有2n+1-(2d-1)片叶子，也即2（n+1）- 2d 大于0 (否则树高就为d-1)。因此有1+log(n+1)>d。又因为2n+12d+1-1，可推得，且d为整数，所以30证明具有n个内点的二叉树中，其平衡二叉树的路径总长为最小。（反证法）若有一高度为d的二叉树T，在其第k层（kd-2）有一叶子x，其d层上有叶子y、z（其一必存在），w为y、z的父结点，若T的路径总长为最小，修改T成T：把y、z挂在x之下，去掉原w下的y、z。则T路径总长T路径总长2d2（k+1）<T路径总长，这与假设条件是矛盾的，也即上面假设的树T是不可能存在的。因此可得平衡二叉树的路径总长最小。31证明二叉判定树的高(n为内点的个数)。因为二叉判定树有n个内点，所以有(n+1)个叶子。树中共有节点2n+1个。假定d为树高，对于高度为d的任何二叉树的节点个数最多为2d+1-1，所以满足2n+1<=2d+1-1，推导得。32证明具有n个内点的二分搜索算法判定树是平衡二叉树。用归纳法证明。n=1时，二分搜索算法判定树是平衡二叉树。假设n<k时，算法判定树均为平衡二叉树，来证n=k时，其结论也成立。事实上，算法判定树是以为根的左右子树构成。l 当k=2l时，左子树上有2l-1-1个内点，左子树高为l-1，其叶子都在l-1层；右子树上有2l-1个内点，右子树高为l，结论成立。l 当k=2l-1时，左右子树上均有2l-1-1个内点，结论成立。l 当2l+1k2l+1-2时，2l-1+（1/2）（k/2）2l-1，2l-1+11（k/2）2l-1，左右子树上均有(k-1)/2个内点（k为奇数）若k为偶数，左子树上有(k/2)-1个内点，左子树高为l。j=，右子树上有（k/2）个内点，右子树高为l。结论成立。得证。33证明用比较算法类中的任一算法，找出n项表中的最大项和最小项，在最坏情况下，至少要比较次。A是比较算法类中的任一算法，S是用A找出L中最大项和最小项所做的比较操作集合，按比较项的胜败情况，S可细分成如下几类：S1：比较的两项都是初次参加比较。S2：比较的两项中，一项是初次参加比较，另一项是在以前的比较中从没有败过。S3：比较的两项中，一项是初次参加比较，另一项是在以前的比较中从没有胜过。S4：比较的两项在以前的比较中都没有败过。S5：比较的两项在以前的比较中都没有胜过。S6：其它情况。显然S1ÈS2ÈS3为找最大项当且仅当要做的比较，S1ÈS3ÈS5为找最小项当且仅当要做的比较。又因为在n项表中找最大项（或最小项）至少要n-1次比较，故知：因此，得证。34证明二叉树所有叶子的深度之和为外路径长epl，二叉树所有内节点的深度之和为内路径长ipl，则有ipl = epl 2n(n为二叉树内节点数目)。用数学归纳法。当n=1时，ipl0,epl=1*2=2,满足ipl = epl 2n。假设当n=k时，满足ipl = epl 2k，现证明当n=k+1时是否满足。假定n=k时，外路径长用epl(k)表示，内路径长用ipl(k)表示，满足ipl(k) = epl(k) 2k。此时，改变其中一个叶子为内节点(假定叶子所在的层数为d)，使得内节点个数为k+1，叶子节点增加1个。改变后的树中，外路径长用epl(k+1)表示，则epl(k+1)epl(k)-d+2(d+1)= epl(k)+d+2，内路径长用ipl(k+1)表示，则ipl(k+1)ipl(k) +d= epl(k) 2k+d= epl(k+1)-d-2-2k+d= epl(k+1)-2(k+1)，得证。35判断题算法是程序的灵魂。对任何算法都必须有输出。对程序和算法都具有有穷性。错算法的分析和实现无关。对算法的输入和输出都不是必需的。错算法语言和程序语言一样，只是说法不同而已。错算法类是指这些算法是解决同一个问题的算法，而基本操作可以不同。错算法的复杂性和算法的结构如何复杂或者如何有技巧性是有关系的。错算法的最坏性态给出了算法工作量的一个上界。对相差一个常数因子的两个函数是同阶的。对在一个函数中，低阶的项不影响函数的阶。对算法的工作量和输入有关。错使一个算法表现得最坏的输入取决于特定的算法，而不是问题本身。对基本运算（基本操作）的选取是可以接受的，仅当所执行的全部运算次数粗略地和基本运算的次数成比例。对仅对于平衡二叉树而言，才满足ipl=epl-2n(n为树的内节点数目)。错具有n个内点的二叉树中，其平衡二叉树的路径总长为最小。对在搜索有序表的比较算法类中，二分搜索算法在平均情况下是最优的。对平衡二叉树中的叶子只可能分布在树的最后两层。对二叉判定树中最长路径上的内节点的个数是算法最坏情况下所做的比较次数。对在求最大次大项问题中，次大项只可能是输给最大项的那些项，假设表中共n项，则次大项的候选者至多有项。对分治法是求解最大最小项问题的最坏情况下的最优算法，而淘汰法不是该问题的最优算法。错在分治法中，使用平衡原则总是可以使算法的效率提高。错36填空题对二叉链表树来说，以_遍历方式遍历，可以得到输入的非递减顺序。中序在n个键值的二叉链表树中搜索的最坏性态是_。O（n）若用epl(I)和ipl(I)分别表示对应输入I（共n个键）所建的二叉链表树的外路径长和内路径长，假定每种输入出现的概率相同，而且成功搜索的概率为1/2，那么二叉链表树搜索的平均性态A(n)可以表示为_。2-3树是均衡的具体含义是_。2-3树的所有叶子在同一层上。（树叶深度相同）假定h为2-3树的高，那么2-3树的叶子数T满足_关系。T在2h和3h之间2-3-4树中的4-结点中有_3_个键。在2-3-4树的4-结点分裂过程中，当4-结点是根时，会分裂成_3个2-结点_。在2-3-4树的4-结点分裂过程中，当4-结点链于2-结点上时，会分裂成_。3-结点下链结2个2-结点在2-3-4树的4-结点分裂过程中，当4-结点链于3-结点上时，会分裂成_。4-结点下链结2个2-结点红黑树的高至多是相应的2-3-4树高的_2_倍。在处理红-黑树的4-结点分裂中，若出现两条相继的红链时，应做_平衡_处理。37问答题二叉链表树有哪些特征？左子树上结点的键（值）都小于根结点的键（值）；右子树上结点的键（值）都不小于根结点的键（值）；任一内结点的左、右子树，都是二叉链表树。在二叉链表树上进行搜索的思想是什么？先将要搜索的键与根结点上的键进行比较，若相等则找到（搜索成功）；若小于根结点的键，到其左子树上搜索；若大于根结点的键，到其右子树上搜索。并把这一思想递归地用到对左、右子树的搜索中，直到搜索成功或未搜索到要搜索的键为止。二叉链表树搜索的最坏情况是什么？w(n)是多少？最坏情况是输入的n个键值呈非递减或递减序时，得到的二叉链表树是一棵“杆”状的退化树。W(n)=O(n)。2-3-4树的建树过程和改进的建树过程有什么不同？并且说明改进的原因。改进的建树过程中，由分裂形成的4-结点，不再立即进行分裂处理，而是留到下次搜索到它时，再进行分裂处理。改进的原因是，这些处理原则可以保证：即使插入键值后产生4-结点，引起结点分裂，也不至于波及到更上层的结点的分裂处理，从而免除分裂导致的额外开销。为什么说2-3树的树叶深度相同？对于2-3-4树来说，当加入一个新的键时，并不直接改变树的深度，只是当新的键加入而引起4-结点的分裂时，才可能改变树的深度，而分裂只有三种类型：4-结点为根结点的分裂；4-结点链接在2-结点下的分裂；4-结点链接在3-结点下的分裂。每种类型的分裂都使得叶子在同一层上。因此2-3树的树叶深度相同。红黑树与二叉链表树和2-3树相比，有哪些优点？与二叉搜索树相比，红黑树搜索效率较高；与2-3-4树相比，红-黑树有统一的数据结构，避免了2-3-4树在建树过程中涉及到4-结点分裂导致的结点类型转换问题，处理较简单。给定一棵2-3-4树，如何把它改造为一棵红-黑树？把2-3-4树上的3-结点、4-结点表示成一棵小树，小树上的结点均是2-结点，且其结点间用红色链链接；原2-3-4树的结点仍用黑色链链接。在二叉链表树上，插入第i个键xi 所做的比较次数、在具有i-1个结点的树上做不成功搜索所需的比较次数与搜索第i个键xi 所作的比较次数三者有什么关系？在二叉链表树上，“插入第i个键xi 所做的比较次数”等于“在具有i-1个结点的树上做不成功搜索所需的比较次数”，又等于“搜索第i个键xi 所作的比较次数减1”。写出二叉链表树搜索Search(v,h)的算法。其中，v是要搜索的结点键值,h是二叉树树根指针。要求，若搜索成功，返回包含键值的结点指针，否则返回空nil。38.二叉树搜索Search(v,h)算法输入：v是要搜索的结点键值,h是二叉树树根指针算法输出：包含键值的结点指针(搜索不成功，结点指针为空nil)1. xh；2. while xz and x->keyv do3. if v<x->Key4. then xx->Left；5. else xx->Right；end;6. if x=z7. then return nil ；8. else return x；39对于给定输入字符序列EASYQUESTION，将其插入空的二叉链表树中，画出建树过程。根据二叉树插入算法，对EASYQUESTION按字母顺序插入后的二叉树如下：对于给定输入字符序列EASYQUESTION，将其插入空的2-3-4树中，画出建树过程。，对于给定输入字符序列EASYQUESTION，将其插入空的红-黑树中，画出建树过程。OESUQTYAIN对于给定输入字符序列INSERTANODE，将其插入空的二叉链表树中，画出建树过程。NTEISA，DO，R给定输入字符序列INSERTANODE，将其插入空的2-3-4树中，画出建树过程。NESAITRDO对于给定输入字符序列INSERTANODE，将其插入空的红-黑树中，画出建树过程。RETALILEVY对于给定输入字符序列RELATIVELY，将其插入空的二叉链表树中，画出建树过程。LEYAIV，YR对于给定输入字符序列RELATIVELY，将其插入空的2-3-4树中，画出建树过对于给定输入字符序列RELATIVELY，将其插入空的红-黑树中，画出建树过程。BEGNIUIJNOYA对于给定输入字符序列BEIJINGAOYUN，将其插入空的二叉链表树中，画出建树过程。JEOG INA BU Y对于给定输入字符序列BEIJINGAOYUN，将其插入空的2-3树中，画出建树过程。对于给定输入字符序列BEIJINGAOYUN，将其插入空的红-黑树中，画出建树过程。JEOBINYAUG40.证明高度为h的23树的顶点个数在2h+1-1和(3h +1-1)/2之间。对于2-3树来说，结点的出度是2或3，叶子又在同一层上，那么每一层上结点数目的最小和最大值如下表所示：层次最少结点数最多结点树0111213122232h2h3h又：所以结点数n满足：41.判断题在二叉链表树中，任一内节点的左、右子树，都是二叉链表树。对按中序遍历二叉链表树，可以得到原输入的非递减顺序。对二叉链表树的建树过程中，如果发现要插入的结点已在树中，则不必插入。错在构建二叉链表树时，仅当输入的n个键值为递减序时，得到的是一棵“杆”状的退化树。错由n个元素输入所建立的二叉链表树有n+1个虚拟结点。对在2-3树的改进的建树过程中，当4-结点的分裂引起其父结点成为新的4-结点时，其父结点暂不分裂。对红黑树的根到其任一叶子的路径上黑链的数目与相对应的2-3-4树上该路径上的黑链数不一定总是相同。错红黑树作为2-3树的变种，一个2-3树唯一对应一个红黑树。错红黑树的路径上的红链数目总是小于等于黑链的数目。对红黑树的高是相应的2-3树高的两倍。错红黑树的根到其任一叶子的路径上不会相继有两条红色链出现。对第二章题库1.填空题若一列键满足下述条件，对任意两个相邻的键，前一个键永不小于后一个键，则称这列键是按_次序排列的。非递增序若一列键满足下述条件，对任意两个相邻的键，前一个键永不大于后一个键，则称这列键是按_次序排列的。非递减序对于在整序过程中仅对键做比较和移动（复写）操作的整序算法，我们称其为_整序算法。键比较 对于值相同的键，如果它们整序前后的相对次序是一样的，则称这种整序方法是_。稳定的一次比较仅移动元素一个位置的任何一个整序算法，对n个元素整序，在平均情况下，至少要比较_次(要求写出函数表达式，而不是函数的阶)。n(n-1)/4选择整序算法的最坏时间复杂度和平均时间复杂度分别是_、_。(n2)，(n2)基于顺序搜索技术的插入整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(n2)，(n2)基于二分搜索技术的插入整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(nlogn)，(nlogn)冒泡整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(n2)，(n2)在非递减序冒泡整序算法中，一趟扫描将_项交换到最终的正确位置上。最大在非递增序冒泡整序算法中，一趟扫描将_项交换到最终的正确位置上。最小在非递减序冒泡整序算法中，一趟扫描可能将非最大项向前滚动_个位置。1快速整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(n2) )，(nlogn)快速整序的分割算法，每次都将_放在最终的正确位置上。标准项如果快速整序算法的分割算法执行时，待分割区有n个键，那么分割算法执行的比较操作的下界是_次。n-1快速整序算法采用的算法设计技术属于_。分治法堆整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(nlogn) )，(nlogn)对于一个项值各不相同的大根堆，最大项肯定位于根结点处，最小项肯定位于_处。叶子如果用一维数组来存储堆，那么下标为i的键的左儿子的下标是_。2i如果用一维数组来存储堆，那么下标为i的键的右儿子的下标是_。2i+1用一维数组存储堆时，如果一个键的下标为i，那么它的父键的下标是_。 用一维数组存储堆时，具有n个结点的堆的最后一个内结点的下标是_。 在平均和最坏情况下，键比较整序算法的时间复杂度下界分别是_、_。O(nlogn)、O(nlogn)任何平均时间复杂度为_的整序算法都可以写出相应的稳定整序算法。O(n2)如果通过键比较来合并两个分别有n个元素的有序表，这样的算法至少要做_次比较运算（要求写出函数表达式，而不是函数的阶）。2n-12简述冒泡整序（结果为非递减序）算法的思想。对待整序的表进行多趟扫描，每趟从第1个键开始依次比较处于相邻位置的一对键，如果它们的顺序不对，就将它们交换，一趟扫描完毕，最大的键被沉淀到表的底部，在随后的扫描中就不再考虑。直到进行了n-1趟扫描或在一趟扫描中没有任何键被交换，算法结束。我们可以对基本的冒泡整序算法加以改进，使得大部分情况下将作更少的比较操作。给出你的改进建议。设置两个指针，分别记录头尾已排好序的位置，每趟排序扫描仅需对这两个指针所指区间的键进行处理，这样就可以避免一些不必要的比较。头指针记录第一次交换发生的位置，如果交换位置j和j+1的键，则头指针指向j-1（由于发生交换，一个较小项被交换到位置j，现在尚不知它与位置j-1的键是否满足次序关系，因此需在下一趟扫描中进行判断），尾指针记录最后一次交换发生的位置，如果交换位置j和j+1的键，则头指针指向j。3请描述将含有n个键的数组L整序成非递减序的冒泡整序算法的最好情况和最坏情况输入，在最好和最坏情况时，冒泡整序算法分别至少要做多少次键的比较？最好情况输入：数组L已呈非递减序，此时算法做n-1次键比较最坏情况输入：数组L呈递减序，此时算法做n(n-1)/2次键比较简述快速整序算法（结果为非递减序）的思想。使用一种分割技术，在待整序的表中任选一个键x作为标准键，将待整序的表分割成三部分：小于x的键、x、大于x的键，此时x已处于正确的位置。然后递归地使用前述技术对第一部分和第三部分（如果存在）进行分割，直到每部分只剩1个键为止。说明快速整序算法的分割算法的功能。从待分割区间中选择一项作为标准项X，将大于X的项安排在X之后，将不大于X的项安排在X之前，最终将标准项X安排在正确的位置并将待分割区间划分为不大于X的键、X、大于X的键三部分。如果待分割区间包含m项，快速整序算法的分割算法至少做多少次键比较才能保证它能正确地工作。如果采用不同的分割机制，你的结论是否仍正确，说明理由。m-1次。无论采用何种分割机制，除X之外的其它项必须与X比较后才能判定其是应该安排在X之前，还是X之后，如果某项不与X比较就不能得到它与X的正确次序关系，因此分割算法必须做m-1次键比较。4如果一个数组L已呈非递减序，那么选择未整序部分首项为标准项的快速整序算法（整序结果为非递减序）做了多少次键比较？做了多少次键的移动？分割算法每次均选择最小的键为标准项，将未整序部分分割为X和大于等于X的部分，因此是快速整序算法的最坏情况，做了n(n-1)/2次键比较，0次键移动如果一个数组L按递减序排列，那么选择未整序部分首项为标准项的快速整序算法（整序结果为非递减序）的执行规律如何？它做了多少次键比较？做了多少次键的移动？快速整序算法的核心是分割算法，这种情况下，分割算法每次均将未整序部分划分为两部分。算法首先选择最大项为标准项，将数组分割为小于等于X的部分和标准项（最大项）X，实际上是做了首项（最大项）和末项（最小项）的交换，接着分割算法选择未整序部分的最小项为标准项，将未整序部分分割为标准项（最小项）X及大于等于X的部分，此时不需要键的移动和交换。重复上述过程，直至将数组整序好。总之，这种情况是快速整序算法的最坏情况，故需做n(n-1)/2次键的比较，当选择未整序部分的最大项为标准项X时，需做2次键移动（最大、最小项交换），当选择最小项为标准项时，不需键移动。由于算法交替地选择最大项、最小项为标准项，故键的移动次数为2* 次。5简述堆整序算法（结果为非递减序）的思想。首先根据堆的定义，将待整序的表建成一个大根堆。然后将堆的最后一个叶子复写到一个临时变量中，将堆顶（根）放在该叶子位置，堆的规模减小1，接着调整去掉堆顶的堆，使放在临时变量中的键与其构成一个新堆。重复上述过程，直到新堆的规模为1为止。用一、二句话来说明堆整序算法的最坏时间复杂度为(nlogn)。因为键比较整序算法的最坏情况下界是(nlogn)，堆整序算法是键比较整序算法，故堆整序算法的最坏情况复杂度为(nlogn)。假设用堆整序算法将一个以递减次序排列的各不相同的键文件整序成递增次序，对于构建堆算法这种输入是最好情况吗？为什么？该输入对于构建堆而言是最好情况。因为对于任意一个内结点，要确定其是否需要向下移动，至少需要比较两次，其中一次用于找出该内结点左右儿子键值的较大值；第二次比较用于将该较大值与内结点本身的键值进行比较。对于一个有n个结点的堆，其内结点数为 ，考虑到最后一个内结点可能只有一个儿子，总的比较次数至少为： 所以当n=10时，总的比较次数为2×519次。因而以递减次序排列的输入是最好情况。假设用堆整序算法将一个以递减次序排列的各不相同的键文件整序成递增次序，若n10，构建堆算法做了多少次比较？若n10，则 ，所以外层“for”循环执行了5次（参见笔记构建堆算法），文件以递减次序排列，故每次for循环中的内层while循环均因不满足k<AM而在首次执行时跳出，比较了两次，第一次for循环由于不满足 而只