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

上机实验 书上 121 页 5。 2 5。 3 书上 151 6。 1 6。 3 6。 6 他说搞懂这几题和实验就没问题了 T(n)= ()2 ( / 2 ) ( )n f n否则足够小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(2f(2k)=2(2 T(2f(2 +f(2k) =22T(221 f(2 f(2k) = =2)+2)+22)+2 0f(2k) =2kg(n)+ 2)+22)+2 0f(2k) 当 g(n)= O(1)和 f(n)= O(n)时， 不妨设 g(n)=a， f(n)=a， 则 T(n)=T(2k)= 22b+22b+2 0*22ka+ =an+O( 当 g(n)= O(1)和 f(n)= O(1)时， 不妨设 g(n)=c， f(n)=d， c， 则 T(n)=T(2k)=2+2 0d=d(2=(c+d)O(n) 一个二分检索的递归过程。 , x, j) if 2/)( if x=A(j if xA(, , x, j); if xA( : ; j 0 (n)= )()3/()( 否则足够小n g(n)= O(1) f(n)= O(1) 成功 : O(1), O(n), O(n) 最好， 平均， 最坏 失败 : O(n), O(n), O(n) 最好， 平均， 最坏 于含有 n 个内部结点的二元树，证明 E=I+2n，其中， E， I 分别为外部和内部路径长度。 证明：数学归纳法 当 n=1时，易知 E=2， I=0，所以 E=I+2n 成立； 假设 n k(k0)时， E=I+2 则当 n=k+1 时，不妨假 定 找到 某个内结点 x 为叶结点（根据二元扩展树的定义，一定存在这样的结点 x，且设该结点的层数 为 h），将结点 结点）从原树中摘除， 生成 新二元扩展树 。 此时新二元扩展树内部结点为 k 个，则满足 k+2k，考察原树的外部路径长度为 = +2h，内部路径长度为 = ，所以 = k+h+1= +2k+2= +2(k+1)， 综合 知 命题成立。 最坏情况时间是 O( 它的最好情况时间是什么 ？能说归并分类的时间是 ( ？ 最好情况 ： 是 对有序文件进行排序 。 分析 ：在此情况下 归并的次数不会发生变化 n)次 归并中比较的次数会发生变化（两个长 n/2序列归并） 最坏情况 两个序列交错大小 ， 需要比较 最好情况 一个序列完全大于 /小于另一个序列 ， 比较 n/2次 差异都是线性的，不改变复杂性的阶 因此 最好情况也是 平均复杂度 可以说 归并分类的时间是 ( 由底向上 ” 的归并分类算法，从而取消对栈空间的利用。 答： 见数据结构 算法 R， n， 1X） 初始化 i1 合并相邻的两个长度为 子文件 i n 2* 1 R， i， i l， i 2*1 X） . ii 2* 处理余留的长度小于 2*子文件 i+1 n j = 1 n Xj X， n， R） . * (确实能得到 12,22的正确值。 P=(22)(22) T=(12)=(22) U=(12) R=12 V=(22) S=21+ =(22)(22) +21-(12)(22) =22112222121212=R+T = 12 21=Q+S = 22 22=P+ =(22)(22)+12+(22)(12) =22112211212121 求以下情况背包问题的最优解， n=7， m=15， ）（71 ,. 10,5,15,7,6,18,3)和 ）（71 ,. 2,3,5,7,1,4,1)。 将以上数据情况的背包问题记为 I。设 )是物品按生成的解， )是一个最优解。问 )/ )是多少 ? 当物品按复 的讨论。 解： 按照ip/(5p/5w， 1p / 1w ，6p/6w，3p/3w，7p/7w， 2p / 2w ， 4p / 4w ) = (6,5,9/2,3,3,5/3,1) 1,2,4,5,1,3,7),解为 (1,1,1,1,1,2/3,0) 所以最优解为：（ 1,2/3,1,0,1,1,1） )=166/3 按照 到 (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) 所以 )的解为（ 1,0,1,4/7,0,1,0） )=47，所以 )/ )=166/141. 按照到 (5w,7w, 1w , 2w ,6w,3w, 4w )=(1,1,2,3,4,5,7) 相应的 (5p,7p, 1p , 2p ,6p,3p, 4p )=(6,3,10,5,18,15,7) 解为 (1,1,1,1,1,4/5,0) 则 )的解为（ 1,1,4/5,0,1,1,1） )=54，所以 )/ )=83/81. 0/1背包问题）如果将 极大化 约束条件 M 或 1 1in 这种背包问题称为 0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按ip/要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。 证明：当按照ip/如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。 可举例如下：设 n=3， M=6，（ 1 p , 2p , 3p） =(3,4,8)，（ 1 w , 2w , 3w）=(1,2,5)，按照ip/1p / 1w , 2p / 2w , 3p/3w） =(3,2,则其解为（ 1,1,0），而事实上最优解是 (1,0,1)，问题得证。 假定要将长为 1l ,2l , n 个程序存入一盘磁带，程序 i 被检索的频率是果程序按 1i ,2i , 期望检索时间（ ni jk ii 1 1 /)( 证明按 证明按 证明按if/最小值。 证明：只需证明结论 是正确的即可，现证明如下： 假设1, 1得到 1+ + ni j , 2j , 且其期望检索式件是 ，我们只需证明 ，即可证明按照if/知 =1+ + ni 妨设程序交换程序到的期望检索时间记为 - =0 显然 也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按if/题得证。 l ,2l , T 和 2T 上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在 1T 和 2T 上的程序集合分别是 ，那么就希望所选择的 使得 Ai Bi 最小值。一种得到 的贪心方法如下：开始将 都初始化为空，然后一次考虑一个程序，如果 Ai il=Ai Bi 则将当前正在考虑的那个程序分配给 A，否则分配给 B。证明无论是按 1l 2l l 2l 种方法都不能产生最优解。 证明：按照 1l 2l 例如下： 3 个程序（ a,b,c）长度分别为（ 1,2,3），根据题中的贪心算法，产生的解是 A=a,cB=b，则 Ai Bi 4，而事实上，最优解应为 3，所以得证 . 按照 1l 2l 例如下： 5 个程序（ a,b,c,d,e）长度分别为（ 10,9,8,6,4）根据题中的贪心算法，产生的解是 A=a,d,eB=b,c，则 Ai Bi 20，而事实上，最优解应为 19，所以得证。 当 n=7， ）（71 ,. 3,5,20,18,1,6,30) 和 ）（71 ,. 1,3,4,3,2,1,2)时，算法 证明即使作业有不同的处理时间定理 里，假定作业 ，要用的处理时间，限期id解： 根据 增 排 序 得 到(7p,3p, 4p ,6p, 2p , 1p ,5p)=(30,20,18,6,5,3,1) ，对应的期限为(2,4,3,1,3,1,2)，按照算法 )=7 )=7,J(2)=3 )=7,J(2)=4,J(3)=3 )=6, J(2)=7,J(3)=4,J(4)=3； 证明：显然即使（id如果 J 中的作业可以按照 的次序而又不违反任何一个期限来处理，即对 次序中的任一个作业 k，应满足kj 下面证明如果 J 是可行解，则使得 , 处理而又不违反任何一个期限 。 因为 必存在 =1r 2r 得对任意的有kj 们设 是按照1,设 ，那么令 br=然 ba，在 中将为然 还要证明为显然二者之间的所有作业有由于 是可行解，所以 bk 以作业有作业可依新产生的排列 =1s 2s 续使用这种方法， 就可转换成 且不违反任何一个期限，定理得证。 已知 (1),A(n 现要将另一存放在 A(n)的元素和 A(1:元素一起构成一个具有 n 个元素的 此写一个计算时间为 O(算法。 在 A(1:n)中存放着一个 一个从堆顶 A(1)删去最小元素后将其余元素调整成 求这新的堆存放在 A(1:，且算法时间为 O( 利用 所写出的算法，写一个对 析这个算法的计算复杂度。 解： ,n) i, j, k j n ; i n/2 i 1 iAj do k Aj; Aj Ai; Ai k j i ; i i/2 ,l,n) i, j, k x An; An Al i 1 j 2*i j j Aj+1) j j+1 xAj) i Aj; i j;j 2*i i n ,n) i, k i= n/2 1 , i, n) i=n 1 k A1; A1 Ai; Ai k , 1, 证明如果一棵树的所有内部节点的度都为 k，则外部节点数 n 1. 证明对于满足 n 1 的正整数 n，存在一棵具有 n 个外部节点的 k 元树 T(在一棵 k 元树中，每个节点的度至多为 k)。进而证明 T 中所有内部节点的度为 k. 证明： 设某棵树内部节点的个数是 m，外部结点的个数是 n，边的条数是 e，则有 e=m+ e=mk mk=m+ (m= n 1 利用数学归纳法。 当 n=1时，存在外部结点数目为 1的 k 元树 T，并且 假设当 n m，且满足 n 1 时，存在一棵具有 n 个外部结点的，且所有内部结点的度为 k； 我们将外部结点数 为 n(n m，且 n 1的最大值 )的符合上述性质的树 结点 知新生成的树 T 中外部结点的数目为 n+(显然 n 为满足 n 1，且比 树 T 每个内结点的度为 k， 即 存在符合性质的树。 综合上述结果可知 ,命题 成立 。 证明如果 n 1，则在定理 面所描述的贪心规则对于所有的（ 1q , 2q , 成一棵最优的 当（ 1q , 2q , 11q ） =（ 3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优 3元归并树。 解： 通过数学归纳法证明： 对于 n=1，返回一棵没有内部结点的树且这棵树显然是最优的。 假定该算法对于（ 1q , 2q , 其中 m =(s+1 (0 s)，都生成一棵最优树 . 则只需证明对于 (1q , 2q , 其中 n=(s+1)+1，也能生成最优树即可。 不失一般性，假定 1q 2q 1q , 2q , 是 1q , 2q , ，设 T 是一棵对于（ 1q , 2q , 最优 k 元归并树。设 P 是距离根最远的一个内部结点。如果 P的 q , 2q , 可以用 1q , 2q , 现在的儿子进行交换，这样不增加 T 的带权外部路径长度。因此 T 也是一棵最优归并树中的子树。于是在 T 中如果用其权为 q1+ + ，则所生成的树 T 是关于 (1q + 2q + + ,一棵最优归并树。由归纳假设，在使用其权为 1q + 2q + + 以后，过程 化成去求取一棵关于 (1q + 2q + + ,最优归并树。因此 q , 2q , 最优归并树。 改过程 其输出每对结点（ i,j）间的最短路径，这个新算法的时 间和空间复杂度是多少？ n, A, i , j, k n, n), A(n, n), n, n), i 1 to n j 1 to n A(i ,j) i ,j) if i j (i, j) i, j ) j i, j) 0 k 1 to n i 1 to n j 1 to n (i,j)A(i,k)+A(k,j) (i,j) A(i,k)+A(k,j) i,j) i,k) i 1 to n j 1 to n do of i to j i ) k i, j) k 0 ,k) k k, j) 间复杂度 O(空间复杂度 O( 证明算法 计算时间是 O( 在已知根 R(i, j)， 0 i j 4 的情况下写一个构造最优二分检索树 明这样的树能在 O(n)时间内构造出来。 解： 将 C 中元素的加法看做基本运算，则算法 时间复杂性为： 20( ( 1 , ) ( , 1 ) 1 )n n i j R i j 20( ( , ) ( , 1 ) 1 )n n i i m R i i m 2( ( 1 , ) ( 0 , 1 ) 1 )n m n R m n m O( m, n, R, (n,n),