计算机算法基础课后答案整理版Word格式文档下载.docx

1、jmid;endifif xA（mid） thenBINSRCH（A, mid+1, high, x, j）;if xBINSRCH（A, low, mid-1, x, j）;elsej0;end BINSRCHP99-5作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。Procedure ThriSearch（A, x, n, j）integer low, high, p1, p2low1; highnwhile lowhighdop1（high+2low）/3 p

2、2（2high+low）/3 case:x=A（p1）: jp1; returnx=A（p2）: jp2;xA（p2）: low p2+1else: lowp1+1; highp2-1end caserepeatj0end ThriSearch实例运行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 361时间复杂度成功:􀂉O（1）,O（log3（n）,O（log3（n）最好，平均，最坏失败:O（log3（n）,O（log3（n）,O（log3（n）P99-6对于含有n个内部结点的二元树，证明E=I+2n其中，E，I分别为外部和内部路径长度。证明：数学归纳

3、法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设nk（k0）时，E=I+2n成立；此时新树内部结点为k个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和内部路径长度：Ek+1= Ek-h+2（h+1） （2）Ik+1=Ik+h（3）综合（1）（2）（3）式：Ek+1= Ik+2k+h+2= Ik+1-h+2k+h+2= Ik+1+2（k+1）故命题成立。P99-10过程MERGESORT的最坏情况时间是O（nlogn），它的最好情况时间是什么？能说归并分类的时间是（nlogn）吗？最好情况：对有序文件进行排序分析归并的次数不会发生变化-log（n）次归并中比较的次数会发生变

4、化（两个长n/2序列归并）最坏情况两个序列交错大小需要比较n-1次最好情况一个序列完全大于/小于另一个序列比较n/2次差异都是线性的，不改变复杂性的阶最好情况也是nlog（n）, 平均复杂度nlog（n）。P99-11写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。见数据结构-第九章P238算法MPass（R，n，1engthX）MP1 初始化i1 MP2 合并相邻的两个长度为length的子文件WHILE i n 2*length + 1 DO（Merge（R，i，ilengthl，i2*length1X）.ii2*length ）MP3 处理余留的长度小于2*length的子文件

5、IF i+length1 0，要用的处理时间ti0，限期diti.解：根据pi的非增排序得到（p7, p3, p4, p6, p2, p1, p5）=（30,20,18,6,5,3,1），对应的期限为（2,4,3,1,3,1,2），按照算法3.5生成的解为：1.J（1）=7（2）,2.J（1）=7（2）, J（2）=3（4）；3.J（1）=7（2）, J（2）=4（3）,J（3）=3（4）；4.J（1）=6（1）, J（2）=7（2）,J（3）=4（3）,J（4）=3（4）；0，限期diti.（P106）定理5.3:设J是K个作业的集合, =i1i2ik是J中作业的一种排序,它使得di1di2

6、dik.J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个期限的情况下来处理.显然即使ti0（diti），如果J中的作业可以按照的次序而又不违反任何一个期限来处理，即对次序中的任一个作业k，应满足dk =kjjt1，则J就是一个可行解。下面证明如果J是可行解， =i1i2ik使得J中的作业可以按照di1di2din 序列排列而又不违反任何一个期限。J是可行解，则必存在=r1r2rn，使得对任意的rk，都有 dk=kjjt1，我们设是按照di1di2din排列的作业序列。假设，那么令a是使raia的最小下标，设rb=ia，显然ba，在中将ra与rb相交换，因为drbdra，显然ra

7、和rb可以按期完成作业，我们还要证明ra和rb之间的作业也能按期完成。因为drbdra，而显然二者之间的所有作业rt，都有drbdrt，又由于是可行解，所以1btbkrrktdd=，所以作业ra和rb交换后，仍满足1ttkrktd=，即所有作业可依新产生的排列=s1s2sn的次序处理而不违反任何一个期限，连续使用这种方法，就可转换成且不违反任何一个期限，定理得证。P123-9对于5.3节的作业排序问题证明：当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；如果J中的作业I还没分配处理时间，则将它分配在时间片a-1，a处理，其中a是使得1rdi的最大整数r，且时间片a-1，a是空的。

8、仿照例5.4的格式，在习题5.8的所提供的数据集上执行算法5.5。易证如果J中的作业能按上述规则处理，显然J是可行解；如果J是可行解，根据定理5.3可知，J中的作业根据时间期限的非降次序排列，得到i1i2ikin，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它的时间期限是dk，且时间片dk-1,dk是空的，则分配之；若时间片dk-1，dk非空，则向前找最大的非空r-1,r时间片，1rdk因为J是可行解，所以一定可以找到如此时间片。故命题得证。n=7（p1, p7）=（3,5,20,18,1,6,30）（d1,d7）=（1,3,4,3,2,1,2）（p7, p3,

9、p4, p6, p2, p1, p5）=（30,20,18,6,5,3,1），对应的期限为（2,4,3,1,3,1,2）b=min n,maxd（i） =min7,4 =4P123-11证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足n mod （k-1）=1.证明对于满足n mod （k-1）=1的正整数n，存在一棵具有n个外部节点的k元树T（在一棵k元树中，每个节点的度至多为k）。进而证明T中所有内部节点的度为k.设某棵树内部节点的个数是i，外部结点的个数是n，边的条数是e，则有e=i+n-1ik=eik=i+n-1（k-1）i=n-1n mod （k-1）=1P123-12证明

10、如果n mod （k-1）=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,qn）生成一棵最优的k元归并树。（P111）当（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。通过数学归纳法证明：对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于（q1,q2,qm），其中m=（k-1）s+1 （s0），都生成一棵最优树，则只需证明对于（q1,q2,qn），其中n=（k-1）（s+1）+1，也能生成最优树即可。不失一般性，假定q1q2qn，且q1,q2,qk是算法所找到的k棵树的WEIG

11、HT信息段的值。于是q1,q2,qk可生成子树T，设T是一棵对于（q1,q2,qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,qk，则可以用q1,q2,qk和P现在的儿子进行交换，这样不增加T的带权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T中如果用其权为q1+q2+qk的一个外部结点来代换T，则所生成的树T是关于（T,qk+1,qn）的一棵最优归并树。由归纳假设，在使用其权为q1+q2+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于（T,qk+1,qn）的最优归并树。因此TREE生成一棵关于（q1,q2,qn）的最优归并树

12、。第六章1 2 3 4 5 6 8 13 17动态规划1.多阶段过程2.满足最优性原理3.建立递推关系式P151-1􀂃递推关系式（6.8）对右图成立吗？为什么？递推关系式（6.8）为什么对于含有负长度环的图不能成立？解：成立，不包含负长度环可以使节点间的长度任意小。P151-2修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？回忆算法：P127 算法6.1P131 算法6.3D（i,j）/D（j） :从节点j到汇点t的最优路径中下一个节点，即最优路径中j的后继节点。算法6.1在计算COST（j）的同时也计算了D（j）37行

13、计算出D（ j ） 之后，即可计算最短路径。911行对矩阵进行初始化，每个元素赋值为边的长度（如果没边则赋值成MAX）15行迭代计算最短路径长度612行仿照6.1，在每次计算最短路径的时候计算出D（j） 再通过D（j） 就可以表示出最短路径for k1 to n do /迭代计算for i1 to n dofor j1 to n doif A（i,j）A（i,k）+A（k,j） thenA（i,j）A（i,k）+A（k,j）Path（i,j）Path（i,k）for i1 to n do/输出最优路径print（“thepath of i to j is ”i ）kpath（i, j）whil

14、e k0 doprint（k）kpath（k, j）end ShortestPath第一个循环：O（n2）O（n3）空间复杂度Cost（n,n） A（n,n） Path（n,n）P151-3对于标识符集（a1,a2,a3,a4）=（end, goto, print, stop），已知成功检索概率为P（1）=1/20, P（2）=1/5, P（3）=1/10, P（4）=1/20，不成功检索概率为Q（0）=1/5, Q（1）=1/10, Q（2）=1/5, Q（3）=1/20, Q（4）=1/20，用算法OBST对其计算W（i,j），R（i, j）和C（i, j）（0i, j4）。P136 算法

15、6.5P（i）P（1）=1/20, P（2）=1/5, P（3）=1/10, P（4）=1/20Q（i）Q（0）=1/5, Q（1）=1/10, Q（2）=1/5, Q（3）=1/20,Q（4）=1/20P（1）=1, P（2）=4, P（3）=2, P（4）=1Q（0）=4, Q（1）=2, Q（2）=4, Q（3）=1, Q（4）=1P151-4证明算法OBST的计算时间是O（n2）。在已知根R（i, j），0i j4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O（n）时间内构造出来。 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：20（1,）（,1）1）nnm

16、miRijRij=+ =20（1,）（,1）1）nnmmiRiimRiim=+ =2（1,）（0,1）1）nmRnmnRmnm=+ O（n2）Procedure BuildTree（m, n, R, Root）integer R（n,n）, kTreeNodeRoot, LR, RRkR（m,n）if k0 then data（Root）k,BuileTree（m, k-1, R, LR）, BuileTree（k, n, R, RR）left（Root）LR, right（Root）RRelse data（Root）m, left（Root）null, right（Root）null, endifend BuildTree时间复杂性分析：T（n）=c+T（k）+T（n-k-1），此递推式保证算法的时间复杂性为O（n），也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O（n）。P151-5由于我们通常只知道成功检索和不成功检索概率的近似值，因此，若能在较短的时间内找出几乎是最优的二分检索树，也是一件很有意义的工作。所谓几乎是最优的二分检索树，就是对