资源描述：
《《算法导论2版》课后答案_加强版2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法导论第三次习题课2008.12.17119.1-1如果x是根节点：degree[sibling[x]]>sibling[x]如果x不是根节点：degree[sibling[x]]=sibling[x]–119.1-3略219.2-2过程略(union操作)19.2-3（1）decrease-key（2）extract-min过程略19.2-6算法思想：找到堆中最小值min，用min-1代替-∞.[遍历堆中树的根节点]315.1-1Print-station(l,I,j)//i为线路，j为stati
2、onifj>1thenPrint-station(l,l[j],j-1)iprint“line”I,“station”j;15.1-2略P195或P32915.1-4f[j]值只依赖f[j-1]的值，从而可以从2n压缩为2个。再加ii上f*、l*、l[j]。i415.2-1略（见课本）15.2-2MATRIX-CHAIN-MULTIPLY(A,s,i,j)ifj>ix=MATRIX-CHAIN-MULTIPLY(A,s,s(i,j),j)y=MATRIX-CHAIN-MULTIPLY(A,s,s(i,
3、j)+1,j)returnMATRIX-MULTIPLY(x,y)elsereturnAi15.2-4略5n15.3-1（归纳法）递归调用Ο(3)n3/2枚举Θ(4/n)15.3-2没有效果，没有重叠子问题15.3-4略615.4-1略（见课本）15.4-2715.4-4815.4-4915.5-3对算法时间复杂度没有影响，但影响程序的性能。15.5-4103¢16.1-1动态规划时间复杂度为O(n),贪心算法时间复杂度为O(n)11¢16.1-2略¢16.1-3用两个链表分别存放空闲教室和繁忙教室，
4、把活动按开始时间递增排序，依次调度教室，就可以获得最少教室数。调度方案是在繁忙教室队列中寻找是否有教室已经空闲，再在空闲教室队列中寻找空闲教室，如果都没有，就再增加一个教室。说明：本题直接调用书上的算法GREDDY-ACTIVITY-SELECTOR()来求是不对的，如下实例，按GREDDY-ACTIVITY-SELECTOR()求得需要3个教室，实际上只要2个教室12¢16.3-1略¢16.3-2略¢16.3-5用2n-1位表示树的结构，内部结点用1表示，叶子结点用0表示。用nlog(n)位表示字母
5、序列，每个字母的二进制编码长度为log(n)，总共需要nlog(n)位。¢17.1-1不能保持，执行n次MULTIPUSH(s,n)¢17.1-3求和，O(n)¢17.2-2每个操作都支付3元费用，若i不是2的幂次，则只用1元，剩下的2元用于支付那些是2的幂次的操作。¢17.2-3当某位被置为1时，用1元支付置位的实际代价，2元作为存款，其中1元将来该位变为0时使用，另外1元RESET此位时使用1317.3-2j假设ik=2+，j是尽可能大的整数，k也是整数。设势能函数Φ()2Di=k当k=0时，有c
6、cˆ=+Φ−Φ()()DDiiii−1jj−1=+−i02(212)i−−jj−1=−i(2(2i−2)2)−j=−+i22=−+ii2=2ccˆ=+Φ−Φ()()DDk≠0时，有iiii−1122(1)=+−kk−=3所以平摊代价为Θ(1)1417.3-6设有两个栈A，BENQUEUE操作为：pushADEQUEUE操作为：ifBisempty将A中元素导入B中ifBisnotemptypopB平摊代价为Ο(1)15¢22.2-2略¢22.2-5如右图¢22.2-7先对T中任意一顶为根做BFS，记录
7、最后遍历的顶点u，再以u为根做BFS，记录最后遍历的顶点v，d(u,v)为T的直径。时间复杂度O(V+E)。16¢22.3-2略¢22.3-3(u(v(y(xx)y)v)u)(w(zz)w)¢22.4-1顺序为pnosmryvxwzuqt¢22.4-2先对图进行拓扑排序，然后从t到s依次计算Pu（以u为起点t为终点的路径数）Pu=∑Pv,v∈Adj(u)Pu=0，出度为0或在t的右边¢22.4-3方法很多，有些方法需要对每个连通片都进行计算。17¢30.2-2DFTis<6,-2+2i,-2,-2-2
8、i>¢30.2-4对FFT算法作如下修改即可：用ω-1代替ω，并且将每个结果元素除以n。18¢30.2-5Tn()3(/3)=Tn+⇒cnTn()=Θ(lg)nn19¢24.1-3略¢24.1-6修改Bellman-Food算法，先找到负环上的一个节点，再依次找到负环上的其他节点。¢24.2-2略¢24.2-4先进行拓扑排序，然后从右往左依次计算Pu（以u为起点的路径数）Pu=∑（Pv+1）,v∈Adj(u)Pu=0，u的出度为0最后对所有Pu累加就是路
