2022年《计算机算法基础》第三版,课后习题答案 .pdf

《2022年《计算机算法基础》第三版,课后习题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年《计算机算法基础》第三版,课后习题答案 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.2 在下列情况下求解递归关系式 T(n)= ()2(/ 2)()g nTnfn否则足够小n当n=2k g(n)= O(1) 和 f(n)= O(n) ；n=2k g(n)= O(1) 和 f(n)= O(1) 。解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) =, =2kT(1)+2k-1f(2)+2k-2f(22)+,+20f(2k) =2kg(n)+ 2k-1f(2)+2k-2f(22)+,+20f(2k) 当 g(n)= O(1) 和 f(n)= O(n) 时，

2、不妨设 g(n)=a ，f(n)=bn ，a，b 为正常数。则 T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+,+20*2kb =2ka+kb2k=an+bnlog2n= O(nlog2n) 当 g(n)= O(1) 和 f(n)= O(1) 时，不妨设 g(n)=c ，f(n)=d ，c，d 为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+,+20d=c2k+d(2k-1) =(c+d)n-d= O(n) 4.3 根据教材中所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j) i

3、nteger mid if lowhigh then mid2/)(highlow if x=A(mid) then jmid; endif if xA(mid) then BINSRCH(A, mid+1, high, x, j); endif if xA(mid) then BINSRCH(A, low, mid-1, x, j); endif else j0; endif end BINSRCH 4.5 作一个“三分”检索算法。它首先检查n/3 处的元素是否等于某个x 的值，然后检查 2n/3 处的元素； 这样，或者找到 x，或者把集合缩小到原来的1/3 。分析此算法在各种情况下的计算复

4、杂度。Procedure ThriSearch(A, x, n, j) integer low, high, p1, p2 low1; high n while low high do p1 3/)2(highlow ; p2 3/)2(highlow case :x=A(p1): jp1; return :x=A(p2): jp2; return 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - :xA(p2): lowp2+

5、1 :else: lowp1+1; highp2-1 end case repeat j 0 end ThriSearch T(n)= )()3/()(nfnTng否则足够小ng(n)= O(1) f(n)= O(1) 成功: O(1), O(log3(n), O(log3(n) 最好，平均，最坏失败: O(log3(n), O(log3(n), O(log3(n) 最好，平均，最坏4.6 对于含有 n 个内部结点的二元树，证明E=I+2n，其中， E，I 分别为外部和内部路径长度。证明：数学归纳法当 n=1时，易知 E=2，I=0 ，所以 E=I+2n 成立；假设 nk(k0) 时，E=I+

6、2n 成立；则当 n=k+1 时，不妨假定找到某个内结点x 为叶结点（根据二元扩展树的定义， 一定存在这样的结点x，且设该结点的层数为h） ，将结点 x 及其左右子结点（外结点）从原树中摘除， 生成新二元扩展树。 此时新二元扩展树内部结点为 k 个，则满足 Ek=Ik+2k，考察原树的外部路径长度为Ek+1= Ek- （h-1）+2h，内部路径长度为 Ik+1=Ik+（h-1） ，所以 Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1) ，综合知命题成立。4.10 过程 MERGESORT的最坏情况时间是O(nlogn) ，它的最好情况时间是什么？能说归并分类的时间

7、是 (nlogn) 吗？最好情况：是对有序文件进行排序。分析：在此情况下归并的次数不会发生变化-log(n)次归并中比较的次数会发生变化（两个长n/2 序列归并）最坏情况两个序列交错大小，需要比较n-1 次最好情况一个序列完全大于 / 小于另一个序列，比较n/2 次差异都是线性的，不改变复杂性的阶因此最好情况也是nlogn, 平均复杂度 nlogn 。可以说归并分类的时间是(nlogn) 4.11 写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

8、- - - - 第 2 页，共 11 页 - - - - - - - - - 答：见数据结构算法 MPass （R，n，1engthX）MP1 初始化 i1 MP2 合并相邻的两个长度为length 的子文件 WHILE i n 2*length + 1 DO （Merge（R，i ，i length l ，i 2*length 1X）. ii 2*length ） MP3 处理余留的长度小于2*length的子文件 IF i+length1 n THEN Merge （R，i ，i+length 1，n. X ） ELSE FOR j = i TO n DO XjRj 算法 MSort(R，

9、n) / 直接两路合并排序算法， X是辅助文件，其记录结构与 R相同MS1 初始化 length1 MS2 交替合并 WHILE length n then FOR j = 1 TO n DO RjXj else MPass（X，n，length R）. length2*length ）endif ) 4.23 通过手算证明（ 4.9 ）和(4.10) 式确实能得到 C11,C12,C21和 C22的正确值。P=(A11+A22)(B11+B22) T=(A11+A12)B22Q=(A21+A22)B11 U=(A21-A11)(B11+B12) R=A11(B12-B22) V=(A12-A

10、22)(B21+B22) S=A22(B21-B11) C11=P+S-T+V =(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22) =A11B11+A22B11+A11B22+A22B22+A22B21 -A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22=A11B11 +A12B21C12=R+T = A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22C21=Q+S = A21B11+A22B11 +A22B21-A22B11

11、 = A21B11 +A22B21 C22=P+R-Q+U =(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - =A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12-A11B11-A11B12=A22B22+A21

12、B125.2 求以下情况背包问题的最优解， n=7， m=15 ，）（71,. pp=(10,5,15,7,6,18,3)和）（71,. ww=(2,3,5,7,1,4,1)。 将以上数据情况的背包问题记为I 。设 FG(I) 是物品按ip的非增次序输入时由 GREEDY-KNAPSACK所生成的解， FO(I) 是一个最优解。问FO(I)/ FG(I) 是多少? 当物品按iw的非降次序输入时，重复的讨论。解： 按照ip/iw的非增序可得(5p/5w，1p/1w，6p/6w，3p/3w，7p/7w，2p/2w，4p/4w) = (6,5,9/2,3,3,5/3,1) W的次序为 (1,2,4,

13、5,1,3,7),解为(1,1,1,1,1,2/3,0) 所以最优解为：（1,2/3,1,0,1,1,1）FO(I)=166/3 按照 Pi 的非增次序输入时得到(6p,3p,1p,4p,5p,2p,7p)= (18,15,10,7,6,5,3)，对应的 (6w,3w,1w,4w,5w,2w,7w)= (4,5,2,7,1,3,1) 解为(1,1,1,4/7,0,0,0) 所以 FG(I) 的解为（ 1,0,1,4/7,0,1,0）FG(I)=47 ，所以 FO(I)/ FG(I)=166/141. 按照iw的非降次序输入时得到(5w,7w,1w,2w,6w,3w,4w)=(1,1,2,3,4

14、,5,7) 相应的 (5p,7p,1p,2p,6p,3p,4p)=(6,3,10,5,18,15,7) 解为(1,1,1,1,1,4/5,0) 则 FW(I)的解为（ 1,1,4/5,0,1,1,1）FW(I)=54，所以 FO(I)/ FW(I)=83/81. 5.3 （0/1 背包问题）如果将5.3 节讨论的背包问题修改成极大化nii1p x约束条件Mnii1w x xi=0或 1 1 i n名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - -

15、 - - - - 这种背包问题称为0/1 背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按ip/iw的非增次序考虑这些物品，只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。证明：当按照ip/iw的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。可举例如下：设n=3，M=6 ， （1p, 2p, 3p）=(3,4,8)， （1w, 2w, 3w）=(1,2,5)，按照ip/iw的非增序得到（1p/1w, 2p/2w, 3p/3w）=(3,2,1.6)，则其解为（ 1,1,0 ） ，而事实上最优

16、解是 (1,0,1)，问题得证。5.6 假定要将长为1l,2l,nl的 n 个程序存入一盘磁带，程序i 被检索的频率是if。如果程序按1i,2i,ni的次序存放，则期望检索时间（ERT ）是niinjjkiiflfkj111/)( 证明按il的非降次序存放程序不一定得到最小的ERT 。 证明按if的非增次序存放程序不一定得到最小的ERT 。 证明按if/il的非增次序来存放程序时ERT取最小值。证明：只需证明结论是正确的即可，现证明如下：假 设1il,2il,nil按 照if/il的 非 增 次 序 存 放 ， 即1if/1il2if/2il, nif/nil，则得到 ERT=1if1il+2

17、if(1il+2il)+,+nif(1il+2il+, + nil/niif1假设该问题的一个最优解是按照1j,2j,nj的顺序存放，并且其期望检索式件是TER，我们只需证明ERTTER，即可证明按照if/il的非增次序存放得到的是最优解。易知TER=1jf1jl+2jf(1jl+2jl)+,+njf(1jl+2jl+, + njl)/niif1从前向后考察最优解中的程序， 不妨设程序kj是第一个与其相邻的程序1kj名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页

18、 - - - - - - - - - 存在关系kjf/kjl1kjf/1kjl，则交换程序kj和程序1kj，得到的期望检索时间记为TERTER-TER=kjf1kjl-1kjfkjl0 TERTER显然TER也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按if/il的非增次序来存放得到的顺序。命题得证。5.7. 假定要把长为1l,2l,nl的 n 个程序分布到两盘磁带1T和2T上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在1T和2T上的程序集合分别是 A和 B，那么就希望所选择的

19、A和 B使得 maxAiil,Biil 取最小值。一种得到 A和 B 的贪心方法如下： 开始将 A和 B都初始化为空， 然后一次考虑一个程序，如果Aiil=minAiil,Biil ，则将当前正在考虑的那个程序分配给 A，否则分配给 B。证明无论是按1l2l, nl或是按1l2l, nl的次序来考虑程序，这种方法都不能产生最优解。证明：按照1l2l, nl存放不会得到最优解，举例如下：3 个程序（ a,b,c ）长度分别为（ 1,2,3 ） ，根据题中的贪心算法，产生的解是 A=a,cB=b ，则 maxAiil,Biil=4，而事实上，最优解应为3，所以得证. 按照1l2l, nl的次序存放

20、也不会得到最优解，举例如下：5 个程序（ a,b,c,d,e）长度分别为（ 10,9,8,6,4）根据题中的贪心算法，产生的解是 A=a,d,eB=b,c，则 maxAiil,Biil=20，而事实上， 最优解应为 19，所以得证。5.8. 当 n=7，）（71,. pp=(3,5,20,18,1,6,30) 和）（71,. dd=(1,3,4,3,2,1,2)时，算法 5.5 所生成的解是什么？ 证明即使作业有不同的处理时间定理5.3 亦真。这里，假定作业 I 的效益ip0，要用的处理时间it0，限期idit. 解：根据ip的非增排序得到(7p,3p,4p,6p,2p,1p,5p)=(30,

21、20,18,6,5,3,1)， 对 应 的 期 限 为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - (2,4,3,1,3,1,2)，按照算法 5.4 生成的解为：a.J(1)=7 b.J(1)=7,J(2)=3 c.J(1)=7,J(2)=4,J(3)=3 d.J(1)=6, J(2)=7,J(3)=4,J(4)=3；证明：显然即使it0（idit） ，如果 J 中的作业可以按照的次序而又不违反任何一个期限来处理，即对次序中

22、的任一个作业k，应满足kdkjjt1，则 J 就是一个可行解。下面证明如果 J 是可行解，则使得 J 中的作业可以按照1id,2id,nid排列的序列处理而又不违反任何一个期限。因为 J 是可行解，则必存在=1r2r,nr， 使得对任意的kr， 都有kdkjjt1，我们设是按照1id2id,nid排列的作业序列。 假设，那么令 a 是使arai的最小下标， 设br=ai，显然 ba，在中将ar与br相交换， 因为brdard，显然ar和br可以按期完成作业。还要证明ar和br之间的作业也能按期完成。因为brdard，而显然二者之间的所有作业tr，都有trdbrd，又由于是可行解，所以bkkt1

23、brdtrd。所以作业ar和br交换后，所有作业可依新产生的排列=1s2s,ns的次序处理而不违反任何一个期限，连续使用这种方法，就可转换成且不违反任何一个期限，定理得证。5.10 已知 n-1 个元素已按 min- 堆的结构形式存放在A(1),A(n-1) 。 现要将另一存放在A(n) 的元素和 A(1:n-1) 中元素一起构成一个具有n 个元素的 min-堆。对此写一个计算时间为O(logn) 的算法。 在 A(1:n) 中存放着一个 min- 堆，写一个从堆顶A(1) 删去最小元素后将其余元素调整成min- 堆的算法，要求这新的堆存放在A(1:n-1) 中，且算法时间为 O(logn).

24、 利用所写出的算法， 写一个对 n 个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。解： procedure INSERT(A,n) integer i, j, k jn ; in/2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - while i1 and AiAj do kAj; AjAi; Ai k ji ; i i/2 repeat end INSERT procedure RESTORE(A,l,n) in

25、teger i, j, k xAn; An Al i1 j2*i while jn-1 do if (j Aj+1) then jj+1 endif if (xAj) then AiAj; ij;j2*i else in endif repeat end RESTORE procedure HEAPSORT(A,n) integer i, k for i=n/2 to 1 step 1 do RESTORE(A, i, n) repeat for i=n to 2 step 1 do kA1; A1Ai; Aik RESTORE(A, 1, i-1) repeat end HEAPSORT 5

26、.11 证明如果一棵树的所有内部节点的度都为k， 则外部节点数 n 满足 n mod (k-1)=1. 证明对于满足 n mod (k-1)=1的正整数 n，存在一棵具有n 个外部节点的 k 元树 T(在一棵 k 元树中，每个节点的度至多为k) 。进而证明 T中所有内部节点的度为 k. 证明：设某棵树内部节点的个数是m ，外部结点的个数是n，边的条数是 e，则有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - e=m+n-1和

27、e=mk mk=m+n-1 (k-1)m=n-1 n mod (k-1)=1 利用数学归纳法。当 n=1时，存在外部结点数目为1 的 k 元树 T，并且 T 中内部结点的度为k；假设当 n m ，且满足 n mod (k-1)=1时，存在一棵具有n 个外部结点的k 元树 T，且所有内部结点的度为k；我们将外部结点数为n(n 为满足 nm ，且 n mod (k-1)=1的最大值 ) 的符合上述性质的树 T 中某个外部结点用内部结点a 替代， 且结点 a 生出 k 个外部结点，易知新生成的树T中外部结点的数目为n+(k-1) ，显然 n 为满足 n mod (k-1)=1 ，且比 m大的最小整数

28、， 而树 T每个内结点的度为k，即存在符合性质的树。综合上述结果可知 , 命题成立。5.12 证明如果 n mod (k-1)=1 ，则在定理5.4 后面所描述的贪心规则对于所有的（1q,2q,nq）生成一棵最优的k 元归并树。 当（1q,2q,11q）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3 元归并树。解：通过数学归纳法证明：对于 n=1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于（1q,2q,mq） ，其中 m =(k-1)s+1 (0 s) ，都生成一棵最优树 . 则只需证明对于 (1q,2q,nq)，其中 n=(

29、k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定1q2q, nq，且1q,2q,kq是算法所找到的k棵树的 WEIGHT 信息段的值。 于是1q,2q,kq棵生成子树T，设T是一棵对于（1q,2q,nq）的最优 k 元归并树。设 P是距离根最远的一个内部结点。如果 P的 k 个儿子不是1q,2q,kq，则可以用1q,2q, ,kq和 P现在的儿子进行交换，这样不增加T的带权外部路径长度。 因此T也是一棵最优归并树中的子树。于是在T中如果用其权为 q1+q2+, +qk 的一个外部结点来代换T，则所生成的树T是关于 (1q+2q+, +kq,1kq, , ,nq) 的一棵最优归并树。

30、由归纳假设，在使用其权为1q+2q+, +kq的那个外部结点代换了T以后，过程 TREE转化成去求取一棵关于 (1q+2q+, +kq,1kq, , ,nq) 的最优归并树。 因此 TREE 生成一棵关于(1q,2q,nq) 的最优归并树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 6.2 修改过程 ALL_PATHS，使其输出每对结点（ i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ Procedure Sh

31、ortestPath(COST, n, A, Max) integer i , j, k real COST(n, n), A(n, n), Path(n, n), Max for i1 to n do for j 1 to n do A(i ,j)COST(i ,j) if ij and A(i, j)Max then Path(i, j )j else Path(i, j)0 endif repeat repeat for k1 to n do for i1 to n do for j1 to n do if A(i,j)A(i,k)+A(k,j) then A(i,j)A(i,k)+A(

32、k,j) Path(i,j)Path(i,k) endif repeat repeat repeat for i1 to n do for j1 to n do print(“the path of i to j is ” i ) kpath(i, j) while k0 do print( ,k) kpath(k, j) repeat repeat repeat end ShortestPath 时间复杂度 O(n3)，空间复杂度 O(n2) 6.4 证明算法 OBST 的计算时间是 O(n2) 。在已知根 R(i, j)，0i j4 的情况下写一个构造最优二分检索树T的算法。证明这样的树能

33、在O(n)时间内构造出来。解：将 C 中元素的加法看做基本运算，则算法OBST的时间复杂性为：20(1,)( ,1)1)nnmmiR ijR ij20(1,)( ,1)1)nnmmiR iimR i im2(1,)(0,1)1)nmR nmnRmnmO(n2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - Procedure BuildTree(m, n, R, Root) integer R(n,n), k TreeNo

34、de Root, LR, RR kR(m,n) if k0 then data(Root)k, BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR) left(Root)LR, right(Root)RR else data(Root)m, left(Root)null, right(Root)null, endif end BuildTree 时间复杂性分析： T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为 O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n

35、)。6.8 给出一个使得DKNAP( 算法 6.7) 出现最坏情况的例子，它使得|Si|=2i, 0 in 。还要求对 n 的任意取值都适用。解：取(P1,P2,Pi,)=(W1,W2,Wi,)=(20,21,2i-1,)P 和 W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。 可用归纳法证明此结论。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -