算法题库.doc

《算法题库.doc》由会员分享，可在线阅读，更多相关《算法题库.doc（22页珍藏版）》请在三一办公上搜索。

1、第一章和第三章题库Pascal语言的创始人N.Wirth提出的一个著名公式是：程序_+_。算法，数据结构算法的非形式化定义为，它是一个_。有穷的运算规则序列算法的五个特征是：_、_、_、_、_。确定性，能行性，有穷性，有0个或1个以上的输入，有1个以上的输出问题的可计算程度分为三种：_、_、_。算法不可解，算法可解，实际可解分析算法的五个准则是：_、_、_、_、_。正确性，工作量，空间量，简单性，最优性算法的最坏性态是指_。算法所执行的基本运算的最大次数算法的平均性态是指_。 算法在各种输入情况下所执行的基本运算次数的加权平均在分析算法的工作量时，使用的衡量标准是_。基本操作在分析算法的工作量

2、时，一般从_和_两个方面分析。最坏情况、平均情况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的阶，满足_

3、关系。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算法语言和程序有什么区别？程序算法数据结构，程序设计是算法的实现，是将一个算法的相当详细的描述和它所使用的数据结构变成某一台计算机的程序。二者的区别是：算法语言是算法的描述语言，面向用户，可以用图表、流程图、伪代码等各种形式描述；而程序是在计算机上可以执行的，面向计算机，只能由程序设计语言实现。而且，算法具有有穷性，而程序没有。分析算法的主要目的有哪些？就算法本身而言，可

4、以确定算法的优劣程度，进而选择、修改、构造算法；就算法所解决的问题而言，确定问题实例的可计算程度。2在通常情况下，对算法进行时间复杂度分析时，其基本步骤有哪些？分析算法工作量的步骤有：（1） 确定算法的基本操作（2） 对算法的输入进行分类，并确定每种输入出现的概率（3） 判定每种输入，算法所执行的基本操作次数（4） 按定义式求出算法的时间复杂性3算法的时间复杂度是如何定义的？算法的时间复杂度是算法所执行的基本操作的次数，有平均情况时间复杂度和最坏情况时间复杂度两种提法。4称“解问题P的算法A，在最坏情况下是最优的。”这句话的含义是什么？在解问题P的、和算法A属于同一算法类的任何算法，在最坏情况

5、下所花费的工作量都不比算法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上运行同样的

6、时间可处理的问题规模是多少？可以建立公式，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

7、(n)、f(n)= (g(n)、f(n)=(g(n)中的哪种关系？并加以证明。 c（c0）,所以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，当nn0时，有n2=g(n)成立，所以n2O(g(

8、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

9、分解成两部分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算法描述 二分搜索（B

10、inary 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 x0, 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 ;

11、 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,问如何找出它们三者中的中间一个值？你的算法就比较次数来说是最优的吗？该问题的平均复杂度和最坏情

12、况复杂度（按比较次数为基本操作）是多少？算法输入：整数a,b,c（假定三个整数互不相等）算法输出：a,b,c三者的中间值算法过程：1）Avg(a+b+c)/32）a1|a-Avg|,b1|b-Avg|,c1|c-Avg|3）if a1b1 thenif c1a1 then output(c);else output(a);elseif c1b1 then output(c);else output(b);该算法的平均比较次数和最坏情况下的比较次数都是2次（A(3)=2,W(3)=2），而且作为算法中通过求解最小值来求中间值，比较次数无论最坏还是平均情况都需要两次,因而是比较类算法中的最优算法。

13、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的

14、输入，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 km do begin3） j:=INT(k+m)/2);4） if x=Lj then k:=j+1;6）end;7）j:=(k+m)/28）output(j)算法的判定树则是将原BISE

15、ARCH算法判定树上的叶子结点全部去掉。l 对于最坏情况：由于原BISEARCH算法判定树的高度为，则本题中算法判定树的高度为，所以其最坏情况下的时间复杂度为。l 对于平均性态：由题意可知，本算法输入的情况只有n种，假定每一种输入情况都是等概率发生,那么显然。由于本算法的判定树与书中原BISEARCH算法的判定树相比，去掉了原BISEARCH算法的判定树中全部叶子结点，叶子结点只可能出现在判定数的最后两层上。假定判定数倒数第2层（即层）的叶子结点数为C，并且除最后一层外，判定数的剩余部分为一棵满二叉树。于是得一般情况下：比较次数为1次的输入类 种比较次数为2次的输入类种 比较次数为次的输入类种

16、比较次数为次的输入类种所以该算法的平均复杂度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、b0，有假设，其中,a ,b , d

17、均为整数 , d 0，有假设： 其中n , m均为整数 ，且 md。又因为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

18、+1)个叶子。树中共有节点2n+1个。假定d为树高，对于高度为d的任何二叉树的节点个数最多为2d+1-1，所以满足2n+1=2d+1-1，推导得。32证明具有n个内点的二分搜索算法判定树是平衡二叉树。用归纳法证明。n=1时，二分搜索算法判定树是平衡二叉树。假设nkeyv do3. if vKey4. then xx-Left；5. else xx-Right；end;6. if x=z7. then return nil ；8. else return x；39对于给定输入字符序列EASYQUESTION，将其插入空的二叉链表树中，画出建树过程。根据二叉树插入算法，对EASYQUESTION按

19、字母顺序插入后的二叉树如下：对于给定输入字符序列EASYQUESTION，将其插入空的2-3-4树中，画出建树过程。，对于给定输入字符序列EASYQUESTION，将其插入空的红-黑树中，画出建树过程。OESUQTYAIN对于给定输入字符序列INSERTANODE，将其插入空的二叉链表树中，画出建树过程。NTEISA，DO，R给定输入字符序列INSERTANODE，将其插入空的2-3-4树中，画出建树过程。NESAITRDO对于给定输入字符序列INSERTANODE，将其插入空的红-黑树中，画出建树过程。RETALILEVY对于给定输入字符序列RELATIVELY，将其插入空的二叉链表树中，画

20、出建树过程。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

21、-3树来说，结点的出度是2或3，叶子又在同一层上，那么每一层上结点数目的最小和最大值如下表所示：层次最少结点数最多结点树0111213122232h2h3h又：所以结点数n满足：41.判断题在二叉链表树中，任一内节点的左、右子树，都是二叉链表树。对按中序遍历二叉链表树，可以得到原输入的非递减顺序。对二叉链表树的建树过程中，如果发现要插入的结点已在树中，则不必插入。错在构建二叉链表树时，仅当输入的n个键值为递减序时，得到的是一棵“杆”状的退化树。错由n个元素输入所建立的二叉链表树有n+1个虚拟结点。对在2-3树的改进的建树过程中，当4-结点的分裂引起其父结点成为新的4-结点时，其父结点暂不分裂。

22、对红黑树的根到其任一叶子的路径上黑链的数目与相对应的2-3-4树上该路径上的黑链数不一定总是相同。错红黑树作为2-3树的变种，一个2-3树唯一对应一个红黑树。错红黑树的路径上的红链数目总是小于等于黑链的数目。对红黑树的高是相应的2-3树高的两倍。错红黑树的根到其任一叶子的路径上不会相继有两条红色链出现。对第二章题库1.填空题若一列键满足下述条件，对任意两个相邻的键，前一个键永不小于后一个键，则称这列键是按_次序排列的。非递增序若一列键满足下述条件，对任意两个相邻的键，前一个键永不大于后一个键，则称这列键是按_次序排列的。非递减序对于在整序过程中仅对键做比较和移动（复写）操作的整序算法，我们称其

23、为_整序算法。键比较 对于值相同的键，如果它们整序前后的相对次序是一样的，则称这种整序方法是_。稳定的一次比较仅移动元素一个位置的任何一个整序算法，对n个元素整序，在平均情况下，至少要比较_次(要求写出函数表达式，而不是函数的阶)。n(n-1)/4选择整序算法的最坏时间复杂度和平均时间复杂度分别是_、_。(n2)，(n2)基于顺序搜索技术的插入整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(n2)，(n2)基于二分搜索技术的插入整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(nlogn)，(nlogn)冒泡整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(n2)，(

24、n2)在非递减序冒泡整序算法中，一趟扫描将_项交换到最终的正确位置上。最大在非递增序冒泡整序算法中，一趟扫描将_项交换到最终的正确位置上。最小在非递减序冒泡整序算法中，一趟扫描可能将非最大项向前滚动_个位置。1快速整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(n2) )，(nlogn)快速整序的分割算法，每次都将_放在最终的正确位置上。标准项如果快速整序算法的分割算法执行时，待分割区有n个键，那么分割算法执行的比较操作的下界是_次。n-1快速整序算法采用的算法设计技术属于_。分治法堆整序算法的最坏时间复杂度和平均时间复杂度分别时是_、_。(nlogn) )，(nlogn)对于一个项

25、值各不相同的大根堆，最大项肯定位于根结点处，最小项肯定位于_处。叶子如果用一维数组来存储堆，那么下标为i的键的左儿子的下标是_。2i如果用一维数组来存储堆，那么下标为i的键的右儿子的下标是_。2i+1用一维数组存储堆时，如果一个键的下标为i，那么它的父键的下标是_。 用一维数组存储堆时，具有n个结点的堆的最后一个内结点的下标是_。 在平均和最坏情况下，键比较整序算法的时间复杂度下界分别是_、_。O(nlogn)、O(nlogn)任何平均时间复杂度为_的整序算法都可以写出相应的稳定整序算法。O(n2)如果通过键比较来合并两个分别有n个元素的有序表，这样的算法至少要做_次比较运算（要求写出函数表达

26、式，而不是函数的阶）。2n-12简述冒泡整序（结果为非递减序）算法的思想。对待整序的表进行多趟扫描，每趟从第1个键开始依次比较处于相邻位置的一对键，如果它们的顺序不对，就将它们交换，一趟扫描完毕，最大的键被沉淀到表的底部，在随后的扫描中就不再考虑。直到进行了n-1趟扫描或在一趟扫描中没有任何键被交换，算法结束。我们可以对基本的冒泡整序算法加以改进，使得大部分情况下将作更少的比较操作。给出你的改进建议。设置两个指针，分别记录头尾已排好序的位置，每趟排序扫描仅需对这两个指针所指区间的键进行处理，这样就可以避免一些不必要的比较。头指针记录第一次交换发生的位置，如果交换位置j和j+1的键，则头指针指向

27、j-1（由于发生交换，一个较小项被交换到位置j，现在尚不知它与位置j-1的键是否满足次序关系，因此需在下一趟扫描中进行判断），尾指针记录最后一次交换发生的位置，如果交换位置j和j+1的键，则头指针指向j。3请描述将含有n个键的数组L整序成非递减序的冒泡整序算法的最好情况和最坏情况输入，在最好和最坏情况时，冒泡整序算法分别至少要做多少次键的比较？最好情况输入：数组L已呈非递减序，此时算法做n-1次键比较最坏情况输入：数组L呈递减序，此时算法做n(n-1)/2次键比较简述快速整序算法（结果为非递减序）的思想。使用一种分割技术，在待整序的表中任选一个键x作为标准键，将待整序的表分割成三部分：小于x的

28、键、x、大于x的键，此时x已处于正确的位置。然后递归地使用前述技术对第一部分和第三部分（如果存在）进行分割，直到每部分只剩1个键为止。说明快速整序算法的分割算法的功能。从待分割区间中选择一项作为标准项X，将大于X的项安排在X之后，将不大于X的项安排在X之前，最终将标准项X安排在正确的位置并将待分割区间划分为不大于X的键、X、大于X的键三部分。如果待分割区间包含m项，快速整序算法的分割算法至少做多少次键比较才能保证它能正确地工作。如果采用不同的分割机制，你的结论是否仍正确，说明理由。m-1次。无论采用何种分割机制，除X之外的其它项必须与X比较后才能判定其是应该安排在X之前，还是X之后，如果某项不

29、与X比较就不能得到它与X的正确次序关系，因此分割算法必须做m-1次键比较。4如果一个数组L已呈非递减序，那么选择未整序部分首项为标准项的快速整序算法（整序结果为非递减序）做了多少次键比较？做了多少次键的移动？分割算法每次均选择最小的键为标准项，将未整序部分分割为X和大于等于X的部分，因此是快速整序算法的最坏情况，做了n(n-1)/2次键比较，0次键移动如果一个数组L按递减序排列，那么选择未整序部分首项为标准项的快速整序算法（整序结果为非递减序）的执行规律如何？它做了多少次键比较？做了多少次键的移动？快速整序算法的核心是分割算法，这种情况下，分割算法每次均将未整序部分划分为两部分。算法首先选择最

30、大项为标准项，将数组分割为小于等于X的部分和标准项（最大项）X，实际上是做了首项（最大项）和末项（最小项）的交换，接着分割算法选择未整序部分的最小项为标准项，将未整序部分分割为标准项（最小项）X及大于等于X的部分，此时不需要键的移动和交换。重复上述过程，直至将数组整序好。总之，这种情况是快速整序算法的最坏情况，故需做n(n-1)/2次键的比较，当选择未整序部分的最大项为标准项X时，需做2次键移动（最大、最小项交换），当选择最小项为标准项时，不需键移动。由于算法交替地选择最大项、最小项为标准项，故键的移动次数为2* 次。5简述堆整序算法（结果为非递减序）的思想。首先根据堆的定义，将待整序的表建成

31、一个大根堆。然后将堆的最后一个叶子复写到一个临时变量中，将堆顶（根）放在该叶子位置，堆的规模减小1，接着调整去掉堆顶的堆，使放在临时变量中的键与其构成一个新堆。重复上述过程，直到新堆的规模为1为止。用一、二句话来说明堆整序算法的最坏时间复杂度为(nlogn)。因为键比较整序算法的最坏情况下界是(nlogn)，堆整序算法是键比较整序算法，故堆整序算法的最坏情况复杂度为(nlogn)。假设用堆整序算法将一个以递减次序排列的各不相同的键文件整序成递增次序，对于构建堆算法这种输入是最好情况吗？为什么？该输入对于构建堆而言是最好情况。因为对于任意一个内结点，要确定其是否需要向下移动，至少需要比较两次，其中一次用于找出该内结点左右儿子键值的较大值；第二次比较用于将该较大值与内结点本身的键值进行比较。对于一个有n个结点的堆，其内结点数为 ，考虑到最后一个内结点可能只有一个儿子，总的比较次数至少为： 所以当n=10时，总的比较次数为2519次。因而以递减次序排列的输入是最好情况。假设用堆整序算法将一个以递减次序排列的各不相同的键文件整序成递增次序，若n10，构建堆算法做了多少次比较？若n10，则 ，所以外层“for”循环执行了5次（参见笔记构建堆算法），文件以递减次序排列，故每次for循环中的内层while循环均因不满足kAM而在首次执行时跳出，比较了两次，第一次for循环由于不满足 而只