上机实验 书上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 :x :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的非增次序存 放得到的是最优解。易知 ERT?=[fj1lj1+fj2(lj+lj)+?+fj(lj+lj+?+ lj)]/?fi 12n12nni?1从前向后考察最优解中的程序，不妨设程序jk是第一个与其相邻的程序jk?1存在关系fj/lj≤fj/lj，则交换程序jk和程序jk?1，得到的期望检索时间 kkk?1k?1记为ERT?? ERT??-ERT?=fjkljk?1-fjk?1ljk≤0 ERT?? ≤ERT? 显然ERT??也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。命题得证。 5.7.假定要把长为l1,l2,?, ln的n个程序分布到两盘磁带T1和T2上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在T1和T2上的程序集合分别是A和B，那么就希望所选择的A和B使得max{?i?Ali,?i?Bli}取最小值。一种得到A和B的贪心方法如下：开始将A和B都初始化为空，然后一次考虑一个程序，如果?i?Ali=min{?i?Ali,?i?Bli}，则将当前正在考虑的那个程序分配给A，否则分配给B。证明无论是按l1≤l2≤?≤ln或是按l1≥l2≥?≥ln的次序来考虑程序，这种方法都不能产生最优解。 证明：按照l1≤l2≤?≤ln存放不会得到最优解，举例如下： 3个程序（a,b,c）长度分别为（1,2,3），根据题中的贪心算法，产生的解是A={a,c}B={b}，则max{?i?Ali,?i?Bli}=4，而事实上，最优解应为3，所以得证. 按照l1≥l2≥?≥ln的次序存放也不会得到最优解，举例如下： 5个程序（a,b,c,d,e）长度分别为（10,9,8,6,4）根据题中的贪心算法，产生的解是A={a,d,e}B={b,c}，则max{?i?Ali,?i?Bli}=20，而事实上，最优解应为19，所以得证。 （p1,.....p7）（d1,.....d7）5.8.①当n=7，=(3,5,20,18,1,6,30) 和=(1,3,4,3,2,1,2) 时，算法5.5所生成的解是什么？ ② 证明即使作业有不同的处理时间定理5.3亦真。这里，假定作业I的效益 pi>0，要用的处理时间ti>0，限期di≥ti. 非 增 排 序 得 到 解：①根据 pi的 (p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，对应的期限为(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； ②证明：显然即使ti>0（di≥ti），如果J中的作业可以按照?的次序而又不 k违反任何一个期限来处理，即对?次序中的任一个作业k，应满足dk ≥?tj， j?1则J就是一个可行解。 下面证明如果J是可行解，则使得J中的作业可以按照di,di,?, di排列 12n的序列?处理而又不违反任何一个期限。 k因为J是可行解，则必存在??=r1r2?rn，使得对任意的rk，都有dk≥?tj， j?1我们设?是按照di≤di≤,?,≤di排列的作业序列。假设????，那么令a是使 12nra?ia的最小下标，设rb=ia，显然b>a，在??中将ra与rb相交换，因为dr≤dr， ba显然ra和rb可以按期完成作业。 还要证明ra和rb之间的作业也能按期完成。因为dr≤dr，而显然二者之间 bab的所有作业rt，都有dr>dr，又由于?是可行解，所以?tk≤dr≤dr。所以作 tbbtk?1业ra和rb交换后，所有作业可依新产生的排列???==s1s2?sn的次序处理而不违反任何一个期限，连续使用这种方法，??就可转换成?且不违反任何一个期限，定理得证。 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). ③ 利用②所写出的算法，写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。 解：① procedure INSERT(A,n) integer i, j, k j←n ; i←?n/2? while i≥1 and A[i]>A[j] do k←A[j]; A[j]←A[i]; A[i]←k j←i ; i←?i/2? repeat end INSERT ② procedure RESTORE(A,l,n) integer i, j, k x←A[n]; A[n]←A[l] i←1 j←2*i while j≤n-1 do if (j< n-1) and (A[j]> A[j+1]) then j←j+1 endif if (x>A[j]) then A[i]←A[j]; i←j;j←2*i else i←n 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 k←A[1]; A[1]←A[i]; A[i]←k RESTORE(A, 1, i-1) repeat end HEAPSORT 5.11．① 证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足n mod (k-1)=1. ② 证明对于满足 n mod (k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k. 证明：① 设某棵树内部节点的个数是m，外部结点的个数是n，边的条数是e， 则有 e=m+n-1和 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为满足n≤m，且n mod (k-1)=1的最大值)的符 合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T’中外部结点的数目为n+(k-1)，显然n为满足n mod (k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，即存在符合性质的树。 综合上述结果可知,命题成立。 5.12．① 证明如果n mod (k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,?, qn）生成一棵最优的k元归并树。 ② 当（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 (0 ≤ s)，都生 成一棵最优树. 则只需证明对于(q1,q2,?, qn)，其中n=(k-1)(s+1)+1，也能生成最优 树即可。 不失一般性，假定q1≤q2≤?≤qn，且q1,q2,?, qk是算法所找到的k 棵树的WEIGHT信息段的值。于是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??是关于(q1+q2+?+qk,qk?1,?,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+?+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于(q1+q2+?+qk,qk?1,?,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,?, qn)的最优归并树。 6.2．修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ Procedure ShortestPath(COST, n, A, Max) integer i , j, k real COST(n, n), A(n, n), Path(n, n), Max for i←1 to n do for j←1 to n do A(i ,j)←COST(i ,j) if i≠j and A(i, j)≠Max then Path(i, j )←j else Path(i, j)←0 endif repeat repeat for k←1 to n do for i←1 to n do for j←1 to n do if A(i,j)>A(i,k)+A(k,j) then A(i,j)←A(i,k)+A(k,j) Path(i,j)←Path(i,k) endif repeat repeat repeat for i←1 to n do for j←1 to n do print(“the path of i to j is ” i ) k←path(i, j) while k≠0 do print( ,k) k←path(k, j) repeat repeat repeat end ShortestPath 时间复杂度O(n3)，空间复杂度O(n2) 6.4．①证明算法OBST的计算时间是O(n2)。 ②在已知根R(i, j)，0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。 解：① 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为： nn?mnn?m??(R(i?1,j)?R(i,j?1)?1)???(R(i?1,i?m)?R(i,i?m?1)?1)?m?2i?0m?2i?0n?m?2(R(n?m?1,n)?R(0,m?1)?n?m?1)?O(n2) ② Procedure BuildTree(m, n, R, Root) integer R(n,n), k TreeNode Root, LR, RR k←R(m,n) if k≠0 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)。 6.8．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i, 0≤i 解：取(P1,P2,?,Pi,?)=(W1,W2,?,Wi,?)=(20,21,?,2i-1,?) P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。