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

'上机实验 书上121页 5。2 5。3 书上151 6。1 6。3 6。6他说搞懂这几题和实验就没问题了4.2在下列情况下求解递归关系式T(n)=当①n=2kg(n)=O(1)和f(n)=O(n)；②n=2kg(n)=O(1)和f(n)=O(1)。解:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2T(2k-2)+f(2k-1))+f(2k)=22T(2k-2)+21f(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)时，不妨设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根据教材中所给出的二分检索策略，写一个二分检索的递归过程。ProcedureBINSRCH(A,low,high,x,j)integermidiflow≤highthenmid←ifx=A(mid)thenj←mid;endififx>A(mid)thenBINSRCH(A,mid+1,high,x,j);endififxA(p2):low←p2+1:else:low←p1+1;high←p2-1endcaserepeatj←0endThriSearchT(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的子文件]WHILEi≤n–2*length+1DO（Merge（R，i，i＋length–l，i＋2*length–1．X）.i¬i＋2*length）．MP3[处理余留的长度小于2*length的子文件]IFi+length–1nthenFORj=1TOnDORj←XjelseMPass（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)B22Q=(A21+A22)B11U=(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+A12B21C12=R+T=A11B12-A11B22+A11B22+A12B22=A11B12+A12B22 C21=Q+S=A21B11+A22B11+A22B21-A22B11=A21B11+A22B21C22=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+A21B125.2①求以下情况背包问题的最优解，n=7，m=15，=(10,5,15,7,6,18,3)和=(2,3,5,7,1,4,1)。②将以上数据情况的背包问题记为I。设FG(I)是物品按的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/FG(I)是多少?③当物品按的非降次序输入时，重复②的讨论。解：①按照/的非增序可得(/，/，/，/，/，/，/)=(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的非增次序输入时得到(,,,,,,)=(18,15,10,7,6,5,3)，对应的(,,,,,,)=(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.③按照的非降次序输入时得到(,,,,,,)=(1,1,2,3,4,5,7)相应的(,,,,,,)=(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节讨论的背包问题修改成 极大化约束条件xi=0或11≤i≤n这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按/的非增次序考虑这些物品，只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。证明：当按照/的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。可举例如下：设n=3，M=6，（,,）=(3,4,8)，（,,）=(1,2,5)，按照/的非增序得到（/,/,/）=(3,2,1.6)，则其解为（1,1,0），而事实上最优解是(1,0,1)，问题得证。5.6．假定要将长为,,…,的n个程序存入一盘磁带，程序i被检索的频率是。如果程序按,,…,的次序存放，则期望检索时间（ERT）是①证明按的非降次序存放程序不一定得到最小的ERT。②证明按的非增次序存放程序不一定得到最小的ERT。③证明按/的非增次序来存放程序时ERT取最小值。证明：只需证明结论③是正确的即可，现证明如下：假设,,…,按照/的非增次序存放，即/≥/≥…≥/，则得到ERT=[+(+)+…+(++…+]/假设该问题的一个最优解是按照,,…,的顺序存放，并且其期望检索式件是，我们只需证明≤，即可证明按照/ 的非增次序存放得到的是最优解。易知=[+(+)+…+(++…+)]/从前向后考察最优解中的程序，不妨设程序是第一个与其相邻的程序存在关系/≤/，则交换程序和程序，得到的期望检索时间记为-=-≤0≤显然也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按/的非增次序来存放得到的顺序。命题得证。5.7.假定要把长为,,…,的n个程序分布到两盘磁带和上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在和上的程序集合分别是A和B，那么就希望所选择的A和B使得max{,}取最小值。一种得到A和B的贪心方法如下：开始将A和B都初始化为空，然后一次考虑一个程序，如果=min{,}，则将当前正在考虑的那个程序分配给A，否则分配给B。证明无论是按≤≤…≤或是按≥≥…≥的次序来考虑程序，这种方法都不能产生最优解。证明：按照≤≤…≤存放不会得到最优解，举例如下：3个程序（a,b,c）长度分别为（1,2,3），根据题中的贪心算法，产生的解是A={a,c}B={b}，则max{,}=4，而事实上，最优解应为3，所以得证.按照≥≥…≥的次序存放也不会得到最优解，举例如下：5个程序（a,b,c,d,e）长度分别为（10,9,8,6,4）根据题中的贪心算法，产生的解是A={a,d,e}B={b,c}，则max{,}=20，而事实上，最优解应为19，所以得证。5.8.①当n=7，=(3,5,20,18,1,6,30)和=(1,3,4,3,2,1,2)时，算法5.5所生成的解是什么？ ②证明即使作业有不同的处理时间定理5.3亦真。这里，假定作业I的效益>0，要用的处理时间>0，限期≥.解：①根据的非增排序得到(,,,,,,)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法5.4生成的解为：a.J(1)=7b.J(1)=7,J(2)=3c.J(1)=7,J(2)=4,J(3)=3d.J(1)=6,J(2)=7,J(3)=4,J(4)=3；②证明：显然即使>0（≥），如果J中的作业可以按照s的次序而又不违反任何一个期限来处理，即对s次序中的任一个作业k，应满足≥，则J就是一个可行解。下面证明如果J是可行解，则使得J中的作业可以按照,,…,排列的序列s处理而又不违反任何一个期限。因为J是可行解，则必存在=…，使得对任意的，都有≥，我们设s是按照≤≤,…,≤排列的作业序列。假设¹s，那么令a是使¹的最小下标，设=，显然b>a，在中将与相交换，因为≤，显然和可以按期完成作业。还要证明和之间的作业也能按期完成。因为≤，而显然二者之间的所有作业，都有>，又由于s是可行解，所以≤≤。所以作业和交换后，所有作业可依新产生的排列==…的次序处理而不违反任何一个期限，连续使用这种方法，就可转换成s且不违反任何一个期限，定理得证。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个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。解：①procedureINSERT(A,n)integeri,j,kj←n;i←whilei≥1andA[i]>A[j]dok←A[j];A[j]←A[i];A[i]←kj←i;i←repeatendINSERT②procedureRESTORE(A,l,n)integeri,j,kx←A[n];A[n]←A[l]i←1j←2*iwhilej≤n-1doif(jA[j+1])thenj←j+1endifif(x>A[j])thenA[i]←A[j];i←j;j←2*ielsei←nendifrepeatendRESTORE③procedureHEAPSORT(A,n)integeri,kfori=to1step–1doRESTORE(A,i,n)repeatfori=nto2step–1dok←A[1];A[1]←A[i];A[i]←kRESTORE(A,1,i-1)repeat endHEAPSORT5.11．①证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足nmod(k-1)=1.②证明对于满足nmod(k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.证明：①设某棵树内部节点的个数是m，外部结点的个数是n，边的条数是e，则有e=m+n-1和e=mkmk=m+n-1Þ(k-1)m=n-1Þnmod(k-1)=1②利用数学归纳法。当n=1时，存在外部结点数目为1的k元树T，并且T中内部结点的度为k；假设当n≤m，且满足nmod(k-1)=1时，存在一棵具有n个外部结点的k元树T，且所有内部结点的度为k；我们将外部结点数为n(n为满足n≤m，且nmod(k-1)=1的最大值)的符合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T’中外部结点的数目为n+(k-1)，显然n为满足nmod(k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，即存在符合性质的树。综合上述结果可知,命题成立。5.12．①证明如果nmod(k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（,,…,）生成一棵最优的k元归并树。②当（,,…,）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。解：①通过数学归纳法证明：对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于（,,…,），其中m=(k-1)s+1(0≤s)，都生成一棵最优树.则只需证明对于(,,…,)，其中n=(k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定≤≤…≤，且,,…,是算法所找到的k棵树的WEIGHT信息段的值。于是,,…,棵生成子树，设是一棵对于（,,…,）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是,,…,，则可以用,,…,和P现在的儿子进行交换，这样不增加的带权外部路径长度。因此 也是一棵最优归并树中的子树。于是在中如果用其权为q1+q2+…+qk的一个外部结点来代换，则所生成的树是关于(++…+,,…,)的一棵最优归并树。由归纳假设，在使用其权为++…+的那个外部结点代换了以后，过程TREE转化成去求取一棵关于(++…+,,…,)的最优归并树。因此TREE生成一棵关于(,,…,)的最优归并树。6.2．修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ProcedureShortestPath(COST,n,A,Max)integeri,j,krealCOST(n,n),A(n,n),Path(n,n),Maxfori←1tondoforj←1tondoA(i,j)←COST(i,j)ifi≠jandA(i,j)≠MaxthenPath(i,j)←jelsePath(i,j)←0endifrepeatrepeatfork←1tondofori←1tondoforj←1tondoifA(i,j)>A(i,k)+A(k,j)thenA(i,j)←A(i,k)+A(k,j)Path(i,j)←Path(i,k)endifrepeatrepeatrepeatfori←1tondoforj←1tondoprint(“thepathofitojis”i)k←path(i,j)whilek≠0doprint(,k)k←path(k,j)repeatrepeatrepeatendShortestPath时间复杂度O(n3)，空间复杂度O(n2) 6.4．①证明算法OBST的计算时间是O(n2)。②在已知根R(i,j)，0≤i