0911算法基础第二次习题课 2011.11.24

9.1-1 按照竞争树的办法求最小值需n-1次比较，然后在lgn个与最小值比较过的元素中求出最小值即为原来n个元素的次小值，需lgn-1次比较，所以共需n+lgn-2次比较 9.1-2 题目是要证明3n/2-2是最少的比较次数，而不是要构造出这样的算法。我们把某个元素与其它元素间的大小关系称作一条信息，那么最大元素包含n-1条信息(这个元素比其它n-1个元素都大)，同样，最小元素也包含n-1条信息，同时求出最大和最小元素就需要获得2n-2条信息。未比较过的元素记为N，比较后较小的元素记为S，较大的元素记为L，那么每次比较获得的信息数如下表：

在最坏情况下，只能在两个未比较过的元素间比较才能得到两条信息，其余的比较至多得到一条信息，而未比较过的元素至多有n个，这样为了得到2n-2条消息至少需要n/2+(2n-2-n)=3n/2-2次比较

9.2-4 最坏时Randomized-Partition每次都返回余下元素中最大的一个，划分序列是{9,8,7,6,5,4,3,2,1,0} 9.3-1 每组7个元素时大于x的元素为 ,此时递归式为 用代换法解得复杂度为O(n) 每组3个元素时同理可得递归式为 用代换法解得复杂度为Ω(nlogn)

9.3-2 SELECT中大于x的元素至少为 当n>=140时满足3n/10-6>= ，同理可证小于的情况 9.3-4 通过比较得到的第i小的元素，在比较过程中比这个元素小的元素构成的集合即为i – 1个小数集合，而比较过程中比这个元素大的元素则构成了n – i 个大元素集合。不需要增加比较次数，只需要每次保留比较信息即可 9.3-7算法步骤： 1 找出集合S的中位数i，O(N)； 2 构造新集合S',其中的元素为： S' = { x'= |x-i| | x 属于S}; n次 3 找出集合S'中的第K小的元素d；O(N); 4 对集合S中的每一个元素x，如果|x-i|<=d, 则x是满足要求的元素. n次

12.2-1, 12.2-5, 12.2-6：略 12.3-1 Tree-Insert(T,z) { T-Insert(T,z){ y=root(T); x=root(T); if(y==NIL){ if(key[z]<key[x]) key[y]=key[z]; if(left[x]==NIL) left[y]=NIL; left[x]=key[z]; right[y]=NIL; } else T-Insert(left[x],z); else else T-Insert(y,z); if(right[x]==NIL) } right[x]=key[z]; else T-insert(right[x],z);

12.3-3 中序遍历O(n)，最好情况下是完全二叉树，运行时间为O(nlogn)，最坏情况下是一个链，运行时间O(n^2) 12.3-6 自己定义一个priority，可以是左右子树的高、左右子树的大小或者等概率随机选择一个 13.1-1 略 13.1-2 都不是，红色违反性质4，黑色违反性质5 13.1-6 最多时是红黑相间的满二叉树，而且最底层内结点为红色，此时内结点总数为(2^2k)-1，最少时是全黑的满二叉树，此时内结点总数为 (2^k)-1

13.2.2 BST(Binary Search Tree)上某个结点的旋转次数，是这个结点能够左旋和右旋的次数之和，即非空的右孩子结点和非空的左孩子结点数之和。对BST上所有结点的旋转次数求和，得到BST的边数为n – 1，这就是n – node的BST可能的旋转数目。 13.2.4 首先证明任意的二分查找树可通过至多n-1次旋转变成右行链。 再由对称性可知右行链可通过至多n-1次旋转变成任意的二分查找树，这样任意两棵二分查找树之间的转换至多需要2(n-1)次旋转。

13.2.5 (1)右行链就不可以通过右旋转换成其它的二分查找树。T1中的根变换到T2相应位置，需要O(n);T1两个子树的节点分别为k个和n-k-1个；得递归式： 13.3.1 取成黑色会改变树的黑高度，这样调整起来更麻烦。 13.3.2 略 13.3.5 用归纳法证即可。

13.4-3．删除过程如下： 删去结点8，其他结点颜色不变 删去结点12，则第四条性质不满足，依据case 2 ，结点19改为黑色，结点31改为红色 删去结点19，结点31成为结点38的左孩子，结点31改为黑色 删去结点31，则第四条性质不满足，依据case 2 ，结点41改为红色 删去结点38，结点41成为根结点，改为黑色 删去结点41，树空，结束

14.1-1．函数运行过程大致如下： r=13, i=10, i<r 设X为T的左孩子， 进入r=8, i=10, i>r 设Y为X的右孩子， 进入r=3, i=2, i<r 设Z为Y的左孩子， 进入r=1, i=2, i>r 设M为Z的右孩子， 进入r=1, i=1, i=r 返回M，即值为20的结点

14. 3-6．实现要求的数据结构有多种。一种参考的数据结构可以书中14 14.3-6．实现要求的数据结构有多种。一种参考的数据结构可以书中14.3节介绍的Interval trees作为基础的数据结构，动态集合中的每个值作为结点的 low endpoint，集合中下一个值作为 该结点的high endpoint，再在此基础上增加一个min-gap域，该域存放的值是以该结点为根的树中，所有结点的high endpoint与low endpoint值差异最大的值。 Insert，Delete，Search算法和Interval trees基本相同，时间复杂度为 。 Min-Gap算法的值可直接由根结点的min-gap域的值直接得到，时间复杂度为

19.1-1 if x is root degree(sibing[x])>degree(x) if x is not root degree(sibing[x])=degree(x)-1 19.1-3证明：1）由树的构成可知：x的第i个孩子的二进制表示为x二进制表示的最右0后第i位置反。 由这个性质我们可以得到第i层节点的二进制表示中有k－i个1。 2）包含j个1的节点个数为第i层的个数(k,i)。 3）数学归纳法证明 对i＝0，1时结论成立 假设对i<k,结论都成立，当i＝k时 假设x为root下的第r子树中的节点，由子树根节点的第r位被置反为0 root的度为k－r，子树根节点满足条件。将子树中前r位去掉不影响性质。考虑子树，由假设可知，子树中的节点满足条件，所以，结论成立。

19.2-2 过程略 ( union操作 ) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2-6 算法思想：找到堆中最小值min，用min-1代替-∞. [遍历堆中树的根节点]

15.1-2 由r1(j)= r2(j)=2r1(j+1), r1(n) = 1, 递推可知: r1(j)= 2 n-j 15.1-1 15.1-2 由r1(j)= r2(j)=2r1(j+1), r1(n) = 1, 递推可知: r1(j)= 2 n-j 15.1-4 fi[j]值只依赖fi[j-1]的值，从而可以从2n压缩为2个。再加上f*、l*、2个l数组(大小为n-1)。 Print-station(l, l*, j ) //i为线路，j为station i  l*; if j>1 then Print-station(l, li[j], j-1 ) print “line” I*, “station” j; 初始调用Print-station(l,l*,n)

15.2-1 略 15.2-2 注意：求矩阵乘法结果 15.2-3 略。需要注意： MATRIX-CHAIN-MULTIPLY(A, s, i, j) if j>i x= MATRIX-CHAIN-MULTIPLY(A, s, i，s(i,j) ) y= MATRIX-CHAIN-MULTIPLY(A, s, s(i,j)+1, j) return MATRIX-MULTIPLY(x, y) else return Ai 15.2-3 略。需要注意： 1 应先给出猜测解 2 c应为常数

15.3-1 枚举复杂度 ，递归复杂度 。 递归的稍微好一点。 15.3-2 mergesort没有重叠子问题 15.3-4 fi(j)计算时候使用fi(j-1)，有重复子问题。

15.4-1 略 15.4-2 PRINT_LCS(c,x,y,i,j) if x[i]=y[j] PRINT_LCS(c,x,y,i-1,j-1) print x[i] else if c[i–1,j] >= c[i,j-1] /*向上*/ PRINT_LCS(c,x,y,i-1,j) else PRINT_LCS(c,x,y,i,j-1) /*向左*/

15.4-4 1. c[i,j]只和c[i-1,j-1]，c[i-1,j],c[I,j-1]有关，故矩阵c可压缩成2行。 2. 本质上c[i,j]只和c[i-1,j], c[i,j-1]有关，故只用一个元素保存c[i-1,j]即可。

2Min(m,n)+O(1): LCS_LENGTH(X,Y) m<-LENGTH[X]; n<-LENGTH[Y]; if m<n exchange X<->Y exchange m<->n for i<-0 to n c[0,i]<- 0; c[1,0]<-0; for i<-1 to m for j<-1 to n if X[i]=Y[j] c[1,j]<-c[0,j-1]+1 else if c[0,j] >= c[1,j-1] c[1,j] <- c[0,j] else c[1,j]<- c[1,j-1] for k<-0 to n /*更新计算结果*/ c[0,k]<-c[1,k] return c[1,n] //最后一个必为最大 Min(m,n)+O(1):进一步压缩空间 LCS_LENGTH2(X,Y) m<-LENGTH[X]; n<-LENGTH[Y]; if m<n exchange X<->Y exchange m<->n for i<-0 to n c[i]<-0; d0<-0; //c[i,j-1] for i<-1 to m for j<-1 to n if x[i]=y[j] d1<-c[j-1]+1; //c[i-1,j-1] else if c[j]>d0 d1<-c[j]; //c[i-1,j] else d1<-d0 c[j-1]<-d0; d0<-d1; d1<-0; return c[n]

15.5-3 这个改变不影响时间复杂度，但是影响系数。 15.5-4 第九行替换为： if i=j root[i,j] <- j e[i,j] <- pi+qi-1+qj else for r<- root[i,j-1] to root[i+1,j] do 时间复杂度为

Project2 下周六、周日(12月3日、4日)晚上验收实验，地点电三楼517~519。 实验报告截止日期12月9日晚12:00之前。 实验报告按要求书写，有图有表有曲线有对比。 实验压缩包格式：姓名+学号+project2.rar 内容：实验纯源代码和实验报告(word或者pdf)。

课堂小测 关键字41,12,19,8插入一棵初始为空的红黑树,画出插入过程,从建好的树中连续删除关键字12,19 请给出一个时间 O(n^2) 的算法,使之能找出一个N个数的序列中最长的单调递增子序列.