c. 键值比较次数M(n)
M(n)=2M(n)+2n for n>1 M(1)=0 习题4.2
1.应用快速排序对序列E,X,A,M,P,L,E按字母顺序排序
16
4. 请举一个n个元素数组的例子,使得我们有必须对它使用本节提到的”限位器”.限位
器的值应是多少年来?为什么一个限位器就能满足所有的输入呢? Hints:
With the pivot being the leftmost element, the left-to-right scan will get out of bounds if and only if the pivot is larger than the other elements. Appending a sentinel(限位器) of value equal A[0](or larger than A[0]) after the array’s last element , the quicksort algorithms will stop the index of the left-to-right scan of A[0..n-1] from going beyond position n.
8.设计一个算法对n个实数组成的数组进行重新排列,使得其中所有的负元素都位于正元素之前.这个算法需要兼顾空间和时间效率. Algorithms netbeforepos(A[0..n-1]) //使所有负元素位于正元素之前 //输入:实数组A[0..n-1]
//输出:所有负元素位于于正元素之前的实数组A[0..n-1]
A[-1]←-1; A[n]←1 //限位器 i←0; j←n-1 While i While A[i]≤0 do i←i+1 while A[j]≥0 do j←j-1 swap A[i]and A[j] swap A[i]and A[j] //undo the last swap 当全是非负数或全是非正数时需要限位器. 习题4.3 1.(题略) 17 解: a.由公式4.4得:4次 b.二分查找判定树: 所以,14,31,42,74,85,98需要比较4次 c. Cyesavg?113114?1?1?113114?2?2?113?3?4?113?4?6?4113?3.2 d. Cnoavg??3?2??4?12?5414?3.9 2. 当n=2k时,用反向替换法求下面的递推方程: 当n>1时, Cw(n)=Cw(n/2)+1, Cw(1)=1 (略) 4.如果对于一个100000个元素的数组成功查找的话,使用折半查找比顺序查找要快多少倍? 6． 如何将折半查找应用于范围查找?范围查找就是对于一个有序数组,找出位于给定值L、U之间（包含L、U）的所有元素，L<=U。该算法的最差效率是多少？ Hints: Step1: 检查A[0]≤L，A[n-1]≥U是否成立，若不成立，则无解。否则进入step 2 Step2:在数组A中用二分查找法查找值L，如果查找成功，则返回数组下标m，否则l二分查找结束时的值. Step3: 在数组A中用二分查找法查找值U，如果查找成功，则返回数组下标m，否则r为二分查找结束时的值. 最后，结果就是在数组序号范围在low和high（包含low,high）之间的范围。（low和high是step2和step3的值。） 7． 为折半查找写递归的伪代码。 18 Algorithms BSR(A[o..n-1],K) //折半查找递归算法 //有序子数组A[l..r]和查找键值K //查找成功则输出其下标，否则输出-1 if l>r return -1 else m← (l+r)/2 if K=A[m] return m else if K< A[m] return BSR(A[l..m-1],K) else if K> A[m] return BSR(A[m+1,r],K) 8.设计一个只使用两路比较的折半查找算法，即只用≤和=, 或者只用≥和=. Algorithms TwoWaysBinarySearch(A[o..n-1],K) //二路比较的折半查找 //有序子数组A[l..r]和查找键值K //查找成功则输出其下标，否则输出-1 l←0, r←n-1 while l 19 Visit T’s root Preorder(TL) Preorder(TR) 递归调用次数C(n)=扩展树中内部结点+外部结点=n+(n+1) =2n+1 7.设计一个算法计算有根有序树的高度. Algorithms height(T) //递归计算有根有序树的高度 //输入:一棵有根有序树的高度T //输出:T的高度 i=NumChildren(T) //根的孩子个数 if i=0 return 0 else return max{height(T1),height(T2),…,height(Ti)}+1 8.下面的算法试图计算一棵二叉树中叶子的数量 Algorithms LeafCount(T) //递归计算二叉树中叶子的数量 //输入:一棵二叉树 //输出:T中叶子的数量 if T=NULL return 0 else return LeafCount(TL)+LeafCount(TR) 应为: if T=NULL return 0 //empty tree else if TL =NULL AND TR=NULL return 1 //single-node tree else return LeafCount(TL)+LeafCount(TR) //general case 习题4.6 1.a.为最近对问题的一维版本设计一个直接基于分治技术的算法,并确定它的效率类型 b.对于这个问题,它是一个好算法吗? 解: a. Algorithms ClosestNumber(A[l..r]) //分治计算最近对问题的一维版本 //输入:升序排列的实数子数组A[l..r] //输出:最近数对的距离 If r=l return ∞ Else if r－l=1 return A[r]－A[l] 20