1、算法设计与分析复习题参考答案1什么是算法？算法必须满足的五个特性是什么？算法：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。（有限指令的集合，遵循它可以完成一个特定的任务）.必须满足的五个特性是(遵循以下五条准则)：1 有穷（限）性2 确定性3 可（能）行性4 输入（n0）5 输出（n1）2对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么结果）？对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。事前分析求出该算法的一个时间界限函数；事后测试搜集此算法的执行时间和实际占用空间的统计资料。3证明：若f1(n)=O(g1(n)并且f2(n)= O(g2(n)，
2、那么f1(n) +f2(n)= O(maxg1(n), g2(n)证明：根据f1(n)=O(g1(n)可知，存在正常数C1，当nn0时，使得|f1(n)|C1|g1(n)|；同理，根据f2(n)= O(g2(n)可知，存在正常数C2，当nn0时，使得|f2(n)|C2|g2(n)| 当nn0时，|f1(n)+f2(n)|f1(n)|+|f2(n)|C1|g1(n)|+C2|g2(n)| C1|gk(n)|+C2|gk(n)|（C1+C2）|gk(n)|， 其中gk(n)=maxg1(n),g2(n)，k=1,2当nn0时，取C=（C1+C2），据定义命题得证。4如果f1(n)= (g1(n)并
3、且f2(n)= (g2(n)，下列说法是否正确？试说明之。（a） f1(n) +f2(n)= (g1(n)+ g2(n)（b） f1(n) +f2(n)= (ming1(n), g2(n)（c） f1(n) +f2(n)= (maxg1(n), g2(n)答：（a）和（c）均正确，（b）错误。（a）正确可以根据定义直接证得。（b）错误可举反例。例：f1(n)= 2n，f2(n)=2 n2下面证明（c）正确性.根据上题已经证明f1(n)+f2(n)= O(maxg1(n),g2(n)，下面只需证明f1(n)+f2(n)= (maxg1(n), g2(n)，即存在正常数C，使得|f1(n)+f2(
4、n)|C(maxg1(n), g2(n) 根据f1(n)= (g1(n)并且f2(n)= (g2(n) 得到，当nn0时，存在正常数C1、C2 、C3、C4C1|g1(n)|f1(n)|C3|g1(n)| C2|g2(n)|f2(n)|C4|g2(n)|不妨设maxg1(n), g2(n)= g1(n)由于|f1(n)+f2(n)|f1(n)|-|f2(n)|C1|g1(n)|-C3|g2(n)|=C|maxg1(n), g2(n)|取C|C1-C3|的正常数，由定义得f1(n)+f2(n) = (maxg1(n), g2(n)命题得证。5证明 |log2n|= O(n)证明：对于任意的正整数
5、n，|log2n|log2（n+1）|n+1|2|n|取n0=1，C=2，根据定义知命题成立。6证明 3nlog2n= O(n2)证明：对于任意的正整数n，|3nlog2n|3nlog2n|3|n2|取n0=1，C=3，根据定义知命题成立。7用数学归纳法证明：当n1时，.证明：当n=1时，n(n+1)/2=1，命题成立； 假设n=k-1时，成立;（k2） 当n=k时，=k(k+1)/2综上可知，命题成立。8在下列情况下求解递归关系式 T(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(2
6、k-1)+f(2k)=2(2 T(2k-2)+f(2k-1) +f(2k) =22T(2k-2)+21 f(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，
7、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)9求解递推关系式： 解：构造生成函数求解 分解成幂级数令 则A=-1 B=1 所以10求解递推关系式：解：11求解递推关系式： 解：以为系数，构成生成函数 其中 12分治法的三个步骤是什么？给出使用SPARKS语言描述的分治策略抽象化控制。答:分治法的三个步骤是: 分解 解决 合并用SPARKS语言描述的分治策略抽象化控制为:Procedure DANDC(p,q)Global n,A(1:n);integer m,p,q;If SMALL(p,
8、q)Then return(G(p,q)Else mDIVIDE(p,q)Return(COMBINE(DANDC(p,m), DANDC(m+1,q) Endif End DANDC13根据教材中所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j)integer midif lowhigh then mid if x=A(mid) then jmid; endifif xA(mid) then BINSRCH(A, mid+1, high, x, j); endifif xA(mid) then BINSRCH(A, lo
9、w, mid-1, x, j); endifelse j0; endifend BINSRCH14作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。 Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low1; highnwhile lowhigh do p1 ; p2 case :x=A(p1): jp1; return :x=A(p2): jp2; return :xA(p2): lowp2+1:el
10、se: lowp1+1; highp2-1 end caserepeatj0end ThriSearchT(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)最好，平均， 最坏15对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设nk(k0)时，E=I+2n成立；则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展树的定义，一定存在这样的
11、结点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)，综合知命题成立。16以比较为基础（基本操作）的分类算法最坏情况的时间下界是什么？答： 17对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是什么？简要说明理由。答： 对线性存储的有序表中元素的以比较为基础的检索算法的执行过程都可以用二元判定树来描述
12、。该树的每个内结点表示一次元素比较，因此对检索的最坏情况而言，该树最少含有n个不同的内结点。检索算法最坏时间不大于该树中由根到一个叶子的最长路径长（树高）。对有n个结点的二元树其最小树高为，所以对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是。18简要说明选择问题算法中二次取中值规则的作用。答：通过选择划分元素V使其尽量靠近元素集合的中间可以得到一个最坏情况时间复杂度是O（n）的选择算法。使用二次取中值规则可以选出满足要求的划分元素V。19给出斯特拉森矩阵乘法算法执行时间的递归关系式，并对其求解计算时间复杂度。答：斯特拉森矩阵乘法算法执行时间的递归关系式为： T(n)= 其中a
13、和b是常数。求解这个递归式，得20通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。P=(A11+A22)(B11+B22) T=(A11+A12)B22Q=(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
14、-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22=A11B11 +A12B21C12=R+T= A11B12-A11B22 +A11B22+A12B22= A11B12 +A12B22C21=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+A21B
15、11+A21B12-A11B11-A11B12=A22B22+A21B1221过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是(nlogn)吗？最好情况：是对有序文件进行排序。分析：在此情况下归并的次数不会发生变化-log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小，需要比较n-1次最好情况一个序列完全大于/小于另一个序列，比较n/2次差异都是线性的，不改变复杂性的阶因此最好情况也是nlogn, 平均复杂度nlogn。可以说归并分类的时间是(nlogn)22写一个“由底向上”的归并分类算法，从而取消对栈空
16、间的利用。答：见数据结构算法MPass（R，n，1engthX） MP1 初始化 i1 MP2 合并相邻的两个长度为length的子文件 WHILE i n 2*length + 1 DO （Merge（R，i，ilengthl，i2*length1X）. ii2*length ） MP3 处理余留的长度小于2*length的子文件 IF i+length1 n THEN Merge（R，i，i+length1，n. X） ELSE FOR j = i TO n DO XjRj 算法MSort(R，n) / 直接两路合并排序算法，X是辅助文件，其记录结构与R相同MS1 初始化 length1
17、MS2 交替合并 WHILE length n then FOR j = 1 TO n DO RjXj else MPass（X，n，lengthR）. length2*length）endif)23什么是约束条件？什么是可行解？什么是目标函数？什么是最优解？并举例说明。答：有一类问题，解由输入的某个子集组成，但是这个子集必须满足某些事先给定的条件。那些必须满足的条件称为约束条件。满足约束条件的子集称为可行解。为了衡量可行解的优劣，事先也给出一定的标准，这些标准一般以函数形式给出，称为目标函数。使目标函数取极值的可行解称为最优解。26什么是贪心方法? 给出使用SPARKS语言描述的贪心方法的抽
18、象化控制。答：对求取最优解问题，选取一种度量标准，将输入按度量标准排序，并按此序一次输入一个量。如果这个输入和前面输入产生的在这种度量意义下的部分最优解加在一起产生一个可行解，将其加入形成新的在这种度量意义下的部分最优解；若不能构成一个可行解，则去掉该输入；重复此过程直到将输入枚举完成。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心方法。贪心方法的SPARKS语言描述的抽象化控制为：Procedure GREEDY(A,n) soltion for i1 to n do xSELECT(A) if FEASIBLE(soltion,x) then soltionUNION(solti
19、on,x) endif repeat return(soltion) end GREEDY24 求以下情况背包问题的最优解，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
20、,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)/
21、FW(I)=83/81.25（0/1背包问题）如果将5.3节讨论的背包问题修改成 极大化 约束条件 xi=0或1 1in这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按/的非增次序考虑这些物品，只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。证明：当按照/的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。可举例如下：设n=3，M=6，（, , ）=(3,4,8)，（, , ）=(1,2,5)，按照/的非增序得到（/, /, /）=(3,2,1.6)，则其解为（1,1,0
22、），而事实上最优解是(1,0,1)，问题得证。26假定要将长为, 的n个程序存入一盘磁带，程序i被检索的频率是。如果程序按, 的次序存放，则期望检索时间（ERT）是 证明按的非降次序存放程序不一定得到最小的ERT。 证明按的非增次序存放程序不一定得到最小的ERT。 证明按/的非增次序来存放程序时ERT取最小值。证明：只需证明结论是正确的即可，现证明如下： 假设, 按照/的非增次序存放，即/，则得到 ERT=+(+)+(+ /假设该问题的一个最优解是按照, 的顺序存放，并且其期望检索式件是，我们只需证明，即可证明按照/的非增次序存放得到的是最优解。易知=+(+)+(+ )/从前向后考察最优解中的
23、程序，不妨设程序是第一个与其相邻的程序存在关系/，则交换程序和程序，得到的期望检索时间记为-=-0 显然也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按/的非增次序来存放得到的顺序。命题得证。27.假定要把长为, 的n个程序分布到两盘磁带和上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在和上的程序集合分别是A和B，那么就希望所选择的A和B使得max,取最小值。一种得到A和B的贪心方法如下：开始将A和B都初始化为空，然后一次考虑一个程序，如果=min,，则将当前正在考虑的那个程序分配
24、给A，否则分配给B。证明无论是按或是按的次序来考虑程序，这种方法都不能产生最优解。证明：按照存放不会得到最优解，举例如下：3个程序（a,b,c）长度分别为（1,2,3），根据题中的贪心算法，产生的解是A=a,cB=b，则max,=4，而事实上，最优解应为3，所以得证.按照的次序存放也不会得到最优解，举例如下：5个程序（a,b,c,d,e）长度分别为（10,9,8,6,4）根据题中的贪心算法，产生的解是A=a,d,eB=b,c，则max,=20，而事实上，最优解应为19，所以得证。28.当n=7，=(3,5,20,18,1,6,30) 和=(1,3,4,3,2,1,2)时，算法5.4所生成的解是
25、什么？ 证明即使作业有不同的处理时间定理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处理
26、而又不违反任何一个期限。因为J是可行解，则必存在=，使得对任意的，都有，我们设s是按照,排列的作业序列。假设s，那么令a是使的最小下标，设=，显然ba，在中将与相交换，因为，显然和可以按期完成作业。还要证明和之间的作业也能按期完成。因为，而显然二者之间的所有作业，都有，又由于s是可行解，所以。所以作业和交换后，所有作业可依新产生的排列=的次序处理而不违反任何一个期限，连续使用这种方法，就可转换成s且不违反任何一个期限，定理得证。29 已知n-1个元素已按min-堆的结构形式存放在A(1),A(n-1)。现要将另一存放在A(n)的元素和A(1:n-1)中元素一起构成一个具有n个元素的min-堆。
27、对此写一个计算时间为O(logn)的算法。 在A(1:n)中存放着一个min-堆，写一个从堆顶A(1)删去最小元素后将其余元素调整成min-堆的算法，要求这新的堆存放在A(1:n-1)中，且算法时间为O(logn). 利用所写出的算法，写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。解： procedure INSERT(A,n) integer i, j, k jn ; i while i1 and AiAj do kAj; AjAi; Aik ji ;i repeat end INSERT procedure RESTORE(A,l,n) integer i, j,
28、k xAn;AnAl i1 j2*i while jn-1 do if (j Aj+1) then jj+1endif if (xAj) then AiAj; ij;j2*ielse inendifrepeatend RESTORE procedure HEAPSORT(A,n) integer i, k for i= to 1 step 1 do RESTORE(A, i, n) repeat for i=n to 2 step 1 do kA1; A1Ai; Aik RESTORE(A, 1, i-1) repeat end HEAPSORT30 证明如果一棵树的所有内部节点的度都为k，则
29、外部节点数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=mkmk=m+n-1 (k-1)m=n-1 n mod (k-1)=1 利用数学归纳法。当n=1时，存在外部结点数目为1的k元树T，并且T中内部结点的度为k；假设当 nm，且满足n mod (k-1)=1时，存在一棵具有n个外部结点的k元树T，且所有内部结点的度为k；我们将外部结点数为n(n为
30、满足nm，且n mod (k-1)=1的最大值)的符合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T中外部结点的数目为n+(k-1)，显然n为满足n mod (k-1)=1，且比m大的最小整数，而树T每个内结点的度为k，即存在符合性质的树。综合上述结果可知,命题成立。31 证明如果n mod (k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（, ）生成一棵最优的k元归并树。 当（, ）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。解：通过数学归纳法证明：对于n=1，返回一棵没有内部
31、结点的树且这棵树显然是最优的。假定该算法对于（, ），其中m =(k-1)s+1 (0 s)，都生成一棵最优树.则只需证明对于(, )，其中n=(k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定，且, 是算法所找到的k棵树的WEIGHT信息段的值。于是, 棵生成子树，设是一棵对于（, ）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是, ，则可以用, 和P现在的儿子进行交换，这样不增加的带权外部路径长度。因此也是一棵最优归并树中的子树。于是在中如果用其权为q1+q2+qk的一个外部结点来代换，则所生成的树是关于(+,)的一棵最优归并树。由归纳假设，在使用其权为
32、+的那个外部结点代换了以后，过程TREE转化成去求取一棵关于(+,)的最优归并树。因此TREE生成一棵关于(, )的最优归并树。32对n=7, ( )=(35，30，25，20，15，10，5) 和( )=(4，2，4，3，4，8，3)的有限期作业调度问题使用教材中作业排序的更快算法求解最优解。（要求描述时间片数组F（i）和对应集合的变化过程）33当作业数n7，（p1，p2，p7）（7, 6, 5, 4, 3, 2, 1）（d1，d2，d7）（4, 2, 4, 3, 1, 4, 6）时，利用算法5.5（作业排序的更快算法）求解上述作业排序问题的最优解。（要求按步骤运行并给出集合树的变化情况及当
33、前最优解）。34举例说明最优性原理是什么？最优性原理是指，过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。例如：35举例说明支配规则的内容。36由最优性原理指出的过程的最优决策序列具有的性质是什么？答：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。37什么样的决策过程构成多阶段决策过程？ 答：活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于i 阶段的过程状态，而与i 阶段之前如何到达这种状态的方式无关，这样的过程就构成一个多阶段决策过程。38使用
34、动态规划求解问题的前提条件是什么？试举出两个例子，这两个例子都可以看作是多阶段决策问题，但一个例子可以用动态规划来解，而另一个例子不能用动态规划求解。39修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ Procedure ShortestPath(COST, n, A, Max)integer i , j, kreal COST(n, n), A(n, n), Path(n, n), Maxfor i1 to n do for j1 to n do A(i ,j)COST(i ,j) if ij and A(i, j)Max then
35、Path(i, j )j else Path(i, j)0 endif repeatrepeatfor k1 to n do for i1 to n do for j1 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 repeatrepeatfor i1 to n do for j1 to n do print(“the path of i to j is ” i ) kpath(i, j) while k0 do print( ,k) kpath(k, j) repea
36、t repeatrepeat end ShortestPath时间复杂度O(n3)，空间复杂度O(n2) 40.已知图的邻接矩阵（1）按照每对结点间的最短路径算法ALL-PATH，求每对结点间的最短路径长度矩阵A4 （2）求路径结点矩阵P。P(i,j)表示从i到j的最短路径的第一步结点。P初始如下：（3）根据P和A4，分别给出结点2到结点4，结点1到结点3的最短路径及长度解: 计算得: A1 = P1= A2 = P2=A3 = P3=A4 = P4=结点2到结点4的最短路径长为9，最短路径是214.结点1到结点3的最短路径长为9，最短路径是143.41给出一个使得DKNAP(算法6.7)出现
37、最坏情况的例子，它使得|Si|=2i, 0in。还要求对n的任意取值都适用。解：取(P1,P2,Pi,)=(W1,W2,Wi,)=(20,21,2i-1,)P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。42递推关系式（6.8）对(P151,图6.16)成立吗？为什么？ 递推关系式（6.8）为什么对于含有负长度环的图不能成立？解：成立，不包含负长度环 可以使节点间的长度任意小。43.设0/1背包问题中(w1,w2,w3,w4)=(10,15,6,9),(p1,p2,p3,p4)=(2,5,8
38、,1),对0i4，生成每个fi阶跃点的序偶集合。解：=(0,0) =(2,10)=(0,0), (2,10) =(5,15), (7,25)=(0,0), (2,10), (5,15), (7,25) =(8,6), (10,16) ,(13,21), (15,31)=(0,0), (8,6), (10,16), (13,21), (15,31) =(1,9), (9,15) ,(11,25), (14,30), (16,40)=(0,0), (8,6), (9,15), (10,16), (13,21), (14,30), (15,31), (16,40)44.对于标识符集（a1,a2,a3
39、,a4）=（end, goto, print, stop），已知已知P(1:4)=(1，4，2，1)和Q(0:4)=(4，2，4，1，1)。使用动态规划方法构造一棵最佳二叉排序树（计算出C、W、R阵的结果）。解: 矩阵W 矩阵C 矩阵R 最佳二叉排序树为: endgotostopprintend45.设n=4, 且( )=(do,if,read,while)，已知P(1:4)=(3,3,1,1)和Q(0:4)=(2,3,1,1,1)，使用动态规划方法构造一棵最佳二叉排序树（计算出C、W、R阵的结果）。解: C= W= R=最佳二叉排序树为: IFREADWHILEDO46证明算法OBST的计算时间是O(n2)。 在已知根R(i, j)，0i j4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。解： 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为： O(
