苏州大学计算机硕士算法期末整理
- 格式：pdf
- 大小：2.82 MB
- 文档页数：18
第三章-递归1．统计二叉树高度递归转非递归2．层次遍历递归转非递归，时空复杂度3．求树的叶节点数递归转非递归4．最后三位010（习题3.6）5．第一次010（习题3.7）6．Fabonacci递归转非递归7．欧几里得算法8．递归实现二分检索9．Fabonacci非递归（2）10.补充：证明Tn=T(n/9)+ T(63n/72)+C1n11．MAXMIN递归转非递归第四章-分治1. 稳定快排2. 完全三叉树的成功检索效率（P76有二叉树的）3. 求解递归关系式（习题4.2）4. 二分检索（递归）（习题4.3）5. MAXMIN递归转非递归（习题4.8）（第三章11）6. 稳定快排（习题4.13）7. 补充：证明E=I+2n第五章-贪心1.期限作业2.01背包（习题5.3）3.集合覆盖（习题5.4）4.结点覆盖（习题5.5）5.期限作业（习题5.8）6.最优三元归并树（习题5.12）7.在假定图用邻接表来表示的情况下重写Prim，计算复杂度（习题5.14）8.补充：用集合算法，求图是否有回路9.补充：用集合算法，求图是否为连通图第六章-动规1.最优二分检索树2.三级系统，成本与可靠性3.货郎担问题4.流水线调度问题P150例题6.19 第七章-基本检索与周游设计算法，输出遍历的二叉树第八章-回溯N的R排列分派问题，成本最小子集合数的状态空间树NQ的状态空间树第九章-分枝限界LCKNAP（LC的背包问题）第十章-NP集团最优化问题可约化为集团的判定问题集团判定为NP难问题P问题、NP问题、NP完全问题、CNF 可满足性问题之间的关系【3.1】（1）试给出统计二叉树高度的递归算法；（2）对该递归算法用消除递归法改写递归：procedure TreeDeep (T)if T = null then deep <- 0else ldeep <- TreeDeep(T, lchild)rdeep <- TreeDeep(T, rchild)deep <- Max(ldeep, rdeep)+1endifreturn (deep)end TreeDeep非递归：Procedure TreeDeep(T)STACK(1:8n); top <- 0L1: if T = null then deep <- 0 // r2 else top <- top+1; STACK(top) <- T // r3top <- top+1; STACK(top) <- ldeep // r3top <- top+1; STACK(top) <- rdeep // r3top <- top+1; STACK(top) <- 2 // r4T <- T.lchild // r5goto L1L2: ldeep <- STACK(top); top <- top-1 // r7 top <- top+1; STACK(top) <- T // r3top <- top+1; STACK(top) <- ldeep // r3top <- top+1; STACK(top) <- rdeep // r3top <- top+1; STACK(top) <- 3 // r4T <- T.rchild // r5goto L1 // r6L3: rdeep <- STACK(top); top <- top-1 // r7 deep <- Max(ldeep, rdeep)+1endifif top = 0 then return (deep) // r8else addr <- STACK(top); top <- top-1 // r10rdeep <- STACK(top); top <- top-1 // r11ldeep <- STACK(top); top <- top-1 // r11T <- STACK(top); top <- top-1 // r11top <- top+1; STACK(top) <- deep // r12if addr = 2; then goto L2 endif // r13if addr = 3; then goto L3 endif // r13 endifend TreeDeep【3.2】三、试写出栈层次遍历一颗二叉树的算法，并给出时空复杂度procedure LEVELORDER(T)if T ≠ null thenInit(Q) //初始化队列Q为空call ADDQ(T,Q)loopif EMPTY(Q) then return endifcall DELETEQ(u,Q)print (u)if u.lchild ≠ null thencall ADDQ(u.lchild, Q)endifif u.rchild ≠ null thencall ADDR(u.rchild, Q)endifrepeatendifend LEVELORDER时间复杂度Θ(n) 空间复杂度Θ(n)【3.3】设有如下递归程序，改为非递归，求叶节点个数procedure leaf(T)if T = null then res = 0else if T是叶子then res = 1else lL = leaf(T.lchild)lR = leaf(T.rchild)res = lL+lRendifendifreturn(res)end leaf非递归：procedure leaf(T)global integer S(1:n), lL, lR, res, addrInit(S)L1: if T=n:1 then res = 0elseif T是叶子then res =1elsepush(T);push(lR);push(lL);push(2)T <- T.lchildgoto L1L2: lL <- pop(S)push(T);push(lR);push(lL);push(3)T <- T.rchildgoto L1L3: lR <- pop(S)res = lL+lRendifendifif empty(S) then return reselseaddr <- pop(S)lL <- pop(S)lR <- pop(S)T <- pop(S)push(res)if addr = 2 then goto L2 endifif addr = 3 then goto L3 endif endifend leaf【3.11】将递归过程MAXMIN翻译成在计算机上等价的非递归过程解：procedure MAXMIN(i,j,fmax,fmin)integer i,j,k; integer stack(1:4n)global n, A(1:n)top <- 0L1: case:i=j: fmax <- fmin <- A(i):i=j-1:if A(i) < A(j) thenfmax <- A(j)fmin <- A(i)elsefmax <- A(i)fmin <- A(j)endif:else:mid <- ⌊(i+j)/2⌋top <- top+1; stack(top) <- i; k <- j; j <- mid;top <- top+1; stack(top) <- j; j <- k; k <- ii <- mid+1; top <- top+1; stack(top) <- itop <- top+1; stack(top) <- j; i <- ktop <- top+1; stack(top) <- 2goto L1L2: gmax <- stack(top); top <- top-1gmin <- stack(top); top <- top-1hmax <- stack(top); top <- top-1hmin <- stack(top); top <- top-1endcaseif top = 0 thenfmax <- max(gmax, hmax)fmin <- min(gmin, hmin)elseaddr <- stack(top); top <- top-1j <- stack(top); top <- top-1; i <- stack(top); top <- top-1;j <- stack(top); top <- top-1; i <- stack(top); top <- top-1;top <- top+1; stack(top) <- hmintop <- top+1; stack(top) <- hmaxtop <- top+1; stack(top) <- gmintop <- top+1; stack(top) <- gmaxif addr=2 then goto L2 endifendifend MAXMIN【4.1】quicksort算法是一种不稳定的算法，但如果把A(i)中的值做适当变换，可使A(i)值各不相同，在分类之后，在将A(i)恢复成原来的值A(i)，试给出变换和恢复表达式，并证明该式能满足要求。
解：（1）首先判断A(1:n)中是否有小数，如果有小数，则将它们整体扩大，直到(1:n)中均为整数（2）然后可利用表达式A(i)*n+i-1，将A(1:n)中各关键字置为不等，下面用反证法来证明该式满足要求不妨设 A(i)*n+i-1 = A(j)*n+j-1则n=(j-i)/(A(i)-A(j))因为在A(1:n)中A(i)=A(j)时i≠j，所以此时A(i)*n+i-1≠A(j)*n+j-1又因为经过第一步变换后A(i)A(j)均为整数，则|A(i)-A(j)|≥1所以(j-i)/(A(i)-A(j)) < j即n<j 导致j下标越界，矛盾即利用A(i)*n+i-1变换，可使A(1:n)中各元素不等（3）设X= A(i)*n+i-1，可利用x div n求得A(i)，即恢复证：因为i-1 < n 所以 x div n = A(i)（4）然后再将得到的A(1:n)缩小原来扩大的倍数【4.2】完全三叉树成功检索的时间复杂度对任何一个完全三叉树E=2I+3n设S(n)是成功检索的平均比较次数，则S(n)=I/n + 1设U(n)是不成功检索的平均比较次数，则U(n)=E/(n+1)则 S(n)= I/n + 1 = (E-3n)/2n + 1 = 12[(1+1n)U(n)−1]当n较大时，S(n)≈U(n)=log(n)所以成功检索的平均情况下时间复杂度为Θ(logn)【5.1】当N=7，(p1,p2,...,p7) = (20,3,5,1,18,6,9),(d1,d2,...,d7)=(1,3,4,3,2,1,2)时，求出该带有期限的作业排序的最优解解：按效益P对作业重新排序序号1’2’3’4’5’6’7’作业号：p1 p5 p7 p6 p3 p2 p4效益：20 18 9 6 5 3 1所以，最优解为：J={P1,P5,P2,P3}【6.1】设n=3 (a1,a2,a3) = (do, read, if) 又设成功检索概率P(1:3) = (3,2,1)和不成功检索概率Q(0:3)=(3,3,2,2),用算法OBST计算w(i,j), R(i,j)和C(i,j)最后写出该最优二分检索树解：（1）计算使j-i=1的W(i,j),C(i,j),R(i,j)W(0,1) = W(0,0) + ( P(1) + Q(1) ) = 3 + ( 3 + 3 ) = 9C(0,1) = W(0,1) + min{ C(0,0) + C(1,1) } = 9 + min{0} = 9R(0,1) = 1W(1,2) = W(1,1) + ( P(2) + Q(2) ) = 3 + ( 2 + 2 ) = 7C(1,2) = W(1,2) + min{ C(1,1) + C(2,2) } = 7 + min{0} = 7R(1,2) = 2W(2,3) = W(2,2) + ( P(3) + Q(3) ) = 2 + ( 1 + 2 ) = 5C(2,3) = W(2,3) + min{ C(2,2) + C(3,3) } = 5 + min{0} = 5R(2,3) = 3（2）计算使j-i=2的W(i,j),C(i,j),R(i,j)W(0,2) = W(0,1) + ( P(2) + Q(2) ) = 9 + ( 2 + 2 ) = 13C(0,2) = W(0,2) + min{ C(0,0)+C(1,2), C(0,1)+C(2,2) } = 13 + min{7,9} = 20 R(0,2) = 1W(1,3) = W(1,2) + ( P(3) + Q(3) ) = 7 + ( 1 + 2 ) = 10C(1,3) = W(1,3) + min{ C(1,1)+C(2,3), C(1,2)+C(3,3) } = 10 + min{5,7} = 15 R(1,3) = 2（3）计算使j-i=3的W(i,j),C(i,j),R(i,j)W(0,3) = W(0,2) + ( P(3) + Q(3) ) = 13 + ( 1 + 2 ) = 16C(0,3) = W(0,3) + min{ C(0,0)+C(1,3), C(0,1)+C(2,3), C(0,2)+C(3,3) } = 16 + min{15,14,20} = 30R(0,3) = 2所以最优二分检索树为：即：【6.2】设计一由设备D1，D2，D3组成的三级系统，每种设备占成本分别为25元，20元，15元，可靠性分别为0.8,0.7,0.6，计划建立该系统的投资不得超过95元。
