《计算机算法基础》第三版_课后习题答案

上机实验 书上121页 5。2 5。3 书上151 6。1 6。3 6。6 他说搞懂这几题和实验就没问题了

4.2在下列情况下求解递归关系式

?g(n)n足够小 T(n)= ?

否则?2T(n/2)?f(n)

当①n=2k g(n)= O(1)和f(n)= O(n)；

k

②n=2g(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)

2k-21k-1k

=2T(2)+2 f(2)+ f(2) =??

=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)时，

不妨设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) integer mid

if low≤high then

mid←?(low?high)/2?

if x=A(mid) then j←mid; endif

if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

4.5作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。

Procedure ThriSearch(A, x, n, j)

integer low, high, p1, p2 low←1; high←n while low≤high do

p1←?(2low?high)/3? ; p2←?(low?2high)/3?

case

:x=A(p1): j←p1; return :x=A(p2): j←p2; return :xA(p2): low←p2+1

:else: low←p1+1; high←p2-1

end case

repeat j←0

end ThriSearch

T(n)= ??g(n)?T(n/3)?f(n)

n足够小否则

g(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成立； ②假设n≤k(k>0)时，E=I+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)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？

最好情况：是对有序文件进行排序。

分析：在此情况下归并的次数不会发生变化----log(n)次

归并中比较的次数会发生变化（两个长n/2序列归并）

最坏情况

两个序列交错大小，需要比较n-1次

最好情况

一个序列完全大于/小于另一个序列，比较n/2次

差异都是线性的，不改变复杂性的阶

因此最好情况也是nlogn, 平均复杂度nlogn。 可以说归并分类的时间是Θ(nlogn)

4.11写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。 答：见《数据结构》

算法MPass（R，n，1ength．X）

MP1 [初始化]

i?1 ．

MP2 [合并相邻的两个长度为length的子文件]

WHILE i ≤ n – 2*length + 1 DO

（Merge（R，i，i＋length–l，i＋2*length–1．X）. i?i＋2*length ） ．

MP3 [处理余留的长度小于2*length的子文件] IF i+length–1 < n

THEN Merge（R，i，i+length–1，n. X）

ELSE FOR j = i TO n DO Xj←Rj ▌

算法MSort(R，n) // 直接两路合并排序算法，X是辅助文件，其记录结构与R相同

MS1 [初始化]

length?1 ．

MS2 [交替合并]

WHILE length < n DO

（MPass（R，n，length．X）. length?2*length if length > n

then FOR j = 1 TO n DO Rj←Xj else MPass（X，n，length．R）. length?2*length）

endif )

4.23通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。

P=(A11+A22)(B11+B22) T=(A11+A12)B22

Q=(A21+A22)B11 U=(A21-A11)(B11+B12) R=A11(B12-B22) V=(A12-A22)(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 +A12B21 C12=R+T

= A11B12-A11B22 +A11B22+A12B22 = A11B12 +A12B22

C21=Q+S

= A21B11+A22B11 +A22B21-A22B11 = A21B11 +A22B21 C22=P+R-Q+U

=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12) =A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12 -A11B11-A11B12 =A22B22+A21B12 5.2① 求以下情况背包问题的最优解，n=7，m=15，=(10,5,15,7,6,18,3)（p1,.....p7）和=(2,3,5,7,1,4,1)。 （w1,.....w7） ② 将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/ FG(I)是多少?

③ 当物品按wi的非降次序输入时，重复②的讨论。 解：① 按照pi/wi的非增序可得

(p5/w5，p1/w1，p6/w6，p3/w3，p7/w7，p2/w2，p4/w4) = (6,5,9/2,3,3,5/3,1)

W的次序为(1,2,4,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的非增次序输入时得到

(p6,p3,p1,p4,p5,p2,p7)= (18,15,10,7,6,5,3)，

对应的(w6,w3,w1,w4,w5,w2,w7)= (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.

③ 按照wi的非降次序输入时得到

(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7) 相应的(p5,p7,p1,p2,p6,p3,p4)=(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节讨论的背包问题修改成

n 极大化

?px

ii1n 约束条件 ?wixi?M xi=0或1 1≤i≤n

1这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。

证明：当按照pi/wi的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。

可举例如下：设n=3，M=6，（p1, p2, p3）=(3,4,8)，（w1, w2, w3）=(1,2,5)，按照pi/wi的非增序得到（p1/w1, p2/w2, p3/w3）=(3,2,1.6)，则其解为（1,1,0），而事实上最优解是(1,0,1)，问题得证。

5.6．假定要将长为l1,l2,?, ln的n个程序存入一盘磁带，程序i被检索的频率是fi。如果程序按i1,i2,?, in的次序存放，则期望检索时间（ERT）是

njnik[?(fijj?1?lk?1)]/?fii?1

① 证明按li的非降次序存放程序不一定得到最小的ERT。 ② 证明按fi的非增次序存放程序不一定得到最小的ERT。 ③ 证明按fi/li的非增次序来存放程序时ERT取最小值。 证明：只需证明结论③是正确的即可，现证明如下： 假设li,li12,?, linnn按照fi/li的非增次序存放，即

fi1/li≥fi/li≥?≥fi/li，则得到

122n ERT=[fili+fi(li+li)+?+fi(li+li+?+ li]/?fi

11212n12ni?1假设该问题的一个最优解是按照j1,j2,?, jn的顺序存放，并且其期望检索式件是ERT?，我们只需证明ERT≤ERT?，即可证明按照fi/li的非增次序存

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《计算机算法基础》第三版_课后习题答案在线全文阅读。