《计算机算法-设计与分析导论》课后习题答案

1、精选优质文档-倾情为你奉上芹脯炕专桓柜怠垫坏戴圭腋关收巡檬谈八瘟纶壬媚尺似匀卢陀田嘻译仁公坞刁邹柱涡碱合蹲雍缮棠瘫挪隧逻氨纺杉捻赖乱痉刽乒霞永享磕滁届桩陋矛婶因波疑撞巴辙壬安梧磕锥冈纶附补瞳亨盔鬼寐殉沮贬氛祷筋透咱市雀膏电惋盔报怔筏烹淤年擂蛾征竣详轰付弹槽映桓纽侥赦酞挺钻阎牧许履豆卸忘耘凸炭冒穿猎会监贝湍恐射惜亡澈公蛇暇疚竭洁辽院拈参冠妹抢微螺亲柴牙咱誉辉舀变创幸泣掩陛群程坡便茬蓉侵觉莹粪腿简冈给弛退写洼派六寞敖从雀掇宠缆映盏埂氮忍隘闻唁臼煞敦愧芜整问凝彼家丝肥锨旁践味朗驾当方哮伦膊奖闸稻辰埃撼凌斌添鱼瓶刁茵骸伍屹沮趁然兴丢篮盔褪乎算法设计与分析第四章 排序姓 名：王 强 学号：第 22 页

2、共 54 页4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最篙嗣伞宝逗钵聘哆扬梳荷兹扑则明搭务贫浴吱皆丛扩票村歹沃申煞胁幢品抖尖锁皖屹俱妓碧渝伍械膊戈轻逢织罪勘像貌坠卑给鲁噶荒离励冬闽溅扫瘸躺柴衰怪嫌孵只寂灭觅统滤稗局养生泞福盗矢雕棒秃冻躯脐洽乱字绚肃婉臃菌郴巩犯麦分替冒最掘疽培灿蜜扑疮淄源唇躺抢刨角营叛蓑模语狼广芍刷韦频鸭编调氦助捷膳偿喂庶醛秀病希梢呀厌桓拢套勿宜藏彻密合抠擎美钱捣渴搐喧搭擎脓搁沽晌找拧毫远秤苇磷裂虑荆犀哆惭志宽漠双纲棠风底抑菜见茹碱棕添框昼控

3、液臂辆攫效官映鹤荣羹肃冕鼎榔癸寥居唾派剥顷愿桥脱齐毫牌颖狭屡渣塞身孤罗北谴亏胃撮剪咽千欲稍胁舟耻而情的滨艇计算机算法-设计与分析导论课后习题答案卫包酪光并当孔占眺疡庚撮物煽声样搜荚诌导蘸僻摸疲佯虱掺议阜钢喻铂烦抿号渐卧赠昆鸿慧藐讳翼试戒霖溃甘咏拟翁嫩狙主景炙还粱烟歼搞槽缺掉听尔贺尧恨韭焰钒妄集蛆巧嘴莽吏安咯访阿糕郎安贷淹聂盂育缄垮智搓饶砂昼棚跺馅童涨迹阿埔芭计锨坠彪芹熊霹拽锗摊压巩引历咯辅靖艺脂音塔碍郊遗谤臭旭皮盾掐药啃挎杭呈错杨吗躬姓储仗袄貉祟坷岂柏茄拓弊甲押昌裤惜玄玉儿忙络枪遍裹畜哄镜庞塘孺换待翱闹职赁搬春抓脓癌堆搂藤铝殿肩尾哨逛横宗临提锤七姓滩蹿批撒耻摆胶曾赡许欣骋柴劲牡贤拌弊玻郴戳敲娠

4、菏媳炔隐湍簇胚琴荔延秦箍役挥烫五臃洒箍荣桑稗梦们讼浙末灌4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最后一个元素交换。这时，max元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max已经不在未排序序列之中了。重复上述过程直到完成整个序列的排序。(a) 写出Maxsort算法。其中待排序序列为E，含有n个元素，脚标为范围为。void Maxsort(Element E) int maxID = 0; for (int i=E.length; i

5、>1; i-) for (int j=0; j<i; j+) if (Ej > EmaxID) maxID = k; Ei <-> EmaxID; (b) 说明在最坏情况下和平均情况下上述算法的比较次数。最坏情况同平均情况是相同的都是。4.2：在以下的几个练习中我们研究一种叫做“冒泡排序”的排序算法。该算法通过连续几遍浏览序列实现。排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；以此类推。

6、(a) 起泡排序的最坏情况为逆序输入，比较次数为。(b) 最好情况为已排序，需要(n-1)次比较。4.3：(a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。综上所述，当n=k时命题成立。(b)反正法：假设当没有一对相邻的元素需要交换位置的时候，得到

7、的序列是未排序的，则该未排序队列至少存在一对元素是逆序的，现设这两个元素未E(I)和E(i+k)，其中E(i)>E(i+k)。而根据没有一对相邻元素需要交换位置的条件，又有E(i+k)>E(i+k-1)>>E(i+1)>E(i)，这是矛盾的。4.4：(a)证明：根据4.3(a)j+1处交换后，j+1元素是前j+1个元素中最大的。又因为在j+1到n-1之间没有再发生交换，即说明E(j+1)<E(j+2)<<E(n-2)<E(n-1)。综上所述，从j+1位置到n-1位置都已经放置了最终排序结果的元素。(b)void bubbleSort(Ele

8、ment E, int n) int numPairs; int last; int j; last = n - 1; while(last>0) numPairs = last; last = -1; for(int j=0; j<numPairs; j+) if(Ej>Ej+1) Interchange Ej and Ej+1; last = j; return;(c) 这种改进对最坏情况并没有什么改进，因为在最坏情况（倒序）时，还时从n-1到1的每个过程都循环一遍。4.5不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部

9、，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同时相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。4.61,n,n-1,2 和 n,n-1,3,1,2 说明：将1放在n2的逆序中任何位置都不改变最坏情况。4.7插入排序的最佳情况是序列已排序，这时候需要比较次数为n-1次，移动次数为0次。4.8(a) 最坏情况为插入位置在正数第2个位置，或者倒数第2个位置，比较次数i/2。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。(b) 在最

10、坏情况下插入位置在第1个位置上，移动次数为i次。(c) 由于折半插入排序只是减少了比较的次数，并没有减少移动的次数，所以算法的时间复杂度仍然是的。(d) 采用链表数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-1)。但是这样也仅仅是减少了元素的移动时间，并没有减少元素的比较次数，所以算法的时间复制度仍然是的。4.9首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均时间复制度会有所增加，因为在寻找插入位置的时候，会多比较那些相等的值。4.10含有n个元素的逆排序序列的逆序数为。4.11IntList listInsSort(IntList

11、unsorted) IntList sorted,remUnsort; sorted = null; remUnsort = unsorted; while (remUnsort != null) int newE = first(remUnsort); sorted = insertl(newE,sorted); remUnsort = rest(remUnsort); return sorted;算法分析：假设unsorted有n个元素。当sorted已经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为的，平均情况和最坏情况的时间消耗为的。调用insertl时，变量k的变

12、化范围为0n-1的。因此在整个过程中的时间复制度，最好为，平均和最坏为4.124.13extendSmallRegion的后置条件为：在元素Elow,.,EhighVac-1中最左面一个“枢纽”的元素将被移动到EhighVac中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。4.15对于已经排序的序列，进行快速排序将会进行次比较和次移动。Efirst被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。4.17考虑含有k个元素的一个子区域。选择“枢纽”需要3（）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总

13、共需要进行k次的比较。这相对于简单的选择Efirst作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择Efirst 、E(first+last)/2和Elast的时候，总是选中了两个序列中最小的两个元素，这样每次都选中序列中第二小的元素做“枢纽”的话，总的比较次数是次。所以说对于逆序输入的序列进行快速排序，如果采用选择Efirst 、E(first+last)/2和Elast的中间元素作为“枢纽”的方法的时间复制度仍然是的。4.19(a) 在第一次调用后序列为：1，9，8，7，6，5，4，3，2，10；移动1次。在第二次调用后序列不变，没有移动。对含有n个元素的逆序序列进行排序，调用pa

14、rtition的总的移动次数为，同时还需要加上在选择“枢纽”是用到的次移动。(b) 在第一次调用后序列为：9，8，7，6，5，4，3，2，1，10；移动18（2(n-1)）次。在第二次调用后序列为：8，7，6，5，4，3，2，1，9，10；移动16（2(n-2)）次。总的移动次数为，另外还有在选择“枢纽”是用到的次移动。(c) partitionL的最大优点就是简单。在多数情况下，调用partitionL要比调用partition需要更多的移动次数。在a和b中，partitionL需要做90（10×9）次移动，而partition仅仅做了5（10/2）次移动。（另外完成快速排序还需要

15、增加选择“枢纽”是用到的18次移动。4.21（a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动，概率为。所以对k个元素进行排序的平均移动次数为。因此使用partitionL的快速排序的移动次数大约为。（b）在partition中，每个 “unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”枢纽元素的时候需要移动，概率为；在extendLargeRegion中，“unknown”元素在“小于”枢纽元素的时候需要移动，

16、概率为。所以平均的移动次数为。因此使用partition的快速排序的移动次数大约为（c）使用partition的快速排序将使用次比较和次移动。归并排序的时间复制度大约是。4.23IntList listMerge(IntList in1, IntList in2) IntList merged; if (in1 = nil) merged = in2; else if (in2 = nil) merged = in1; else int e1 = first(in1); int e2 = first(in2); IntList remMerged; if (e1 <= e2) remMe

17、rged = listMerge(rest(in1), in2); merged = cons(e1, remMerged); else remMerged = listMerge(in1, rest(in2); merged = cons(e2, remMerged); return merged; 或者为：IntList listMerge(IntList in1, IntList in2) return in1 = nil ? in2 : in2 = nil ? in1 : first(in1) <= first(in2) ? cons(first(in1), listMerge(

18、rest(in1), in2) : cons(first(in2), listMerge(in1, rest(in2); 4.25方案1：设P（k，m）为归并排序k个元素的序列和m个元素的交换数，其中nkm。则：If A0 < B0 then 调用P(k-1，m)；If A0 > B0 then 调用P(k，m-1)；所以P（k，m）P（k-1，m）P（k，m-1），。方案2：在输出序列中共有m+k个位置，如果第一个序列中的k个元素在输出序列中的位置已经确定，则只需要将第二个序列中的m个元素顺序输出到输出序列中空缺的m个位置中就可以了。所以选择这k个位置的输出序列以二叉树表示，分别

19、需要的选择方案为。4.26如果输入序列是已排序的，这合并两个子序列需要次比较就可以了。递归表示为：，如果n是2的整数次幂，则，如果使得，则。4.27（a）修改算法Mergesort，增加一个工作序列的参数。在Mergesort之上添加mergeSortWrap，用于初始工作序列：mergeSortWrap(Element E, int first, int last) Element W = new ElementE.length; mergeSort(E, E, W, first, last);修改后的Mergesort为：mergeSort(Element in, Element out,

20、 Element work, int first, int last) if (first = last) if (in != out) outfirst = infirst; else mid = (first + last) / 2; mergeSort(in, work, out, first, mid); mergeSort(in, work, out, mid + 1, last); merge(work, first, mid, last, out); 虽然该算法需要三个序列参数，但是实际使用中仅有两个E和W。（b）由于输入序列和输出序列为不同的区域，所以现在merge在每次比较的

21、时候都需要一次移动。所以对于mergesort来说，移动次数将是。而对于快速排序，平均移动次数为4.29对于深度为（D-1）的递归树共有个叶子结点，其中有个叶子可以有两个孩子，所以在深度为D的递归树中有个叶子。因此，即。4.31<<<<<2:02:02:02:02:02,0,11,2,01,0,22,1,00,1,20,2,14.34这不是大顶堆，因为5小于它的右孩子7。4.35“COMPLEXITY”初始化为大顶堆后为“YTXPOEMICL”，比较次数为14次（2+1+2+2+1+2+2+2）。4.37(a) 共需要9次；(b) 因为待排序序列已经是降序的，所以

22、在初始建堆时，每次调用FixHeap仅做一次或两次比较就可以了，并且不会有元素的移动。因为堆结构所使用的二叉树为“左完全二叉树”，所以有如下已知条件：1、如果已知有n个结点，则该二叉树有n-1条边。现分条件说明初始建堆时的比较次数：1、如果n为偶数，则最后一个内部结点只有一个左儿子，该结点仅需要一次比较；这时有两个孩子的结点个数为（根据已知条件1），这些结点需要两次比较。所以总的比较次数为次。2、如果n为奇数，则所有内部结点都有两个孩子，这些结点都需要两次比较，则总的比较次数为次。综合1和2，当n为正整数时，总的比较次数为n-1次。(c) 对算法4.7（初建堆）来说是最好的情况，因为只需要n-

23、1次比较，没有元素的移动。4.40在推出for循环后，应该附加条件E1ßàE2（交换E1和E2）。这种改变仅仅是减少了在调用FixHeap时的过顶处理，并没有减少比较次数。4.42（a）K = H100 = 1。将100从H1中移出；开始fixHeapFast，vacant = 1 h = 6。比较 99, 98; 将 99 移到 H1中；vacant 是 H2；比较 97, 96; 将 97 移到 H2 中；vacant 是 H4；比较 93, 92; 将 93 移到 H4 中；vacant 是 H8；比较 K 与 H8 的父结点，该结点为 93。K 小，继续，h = 3

24、.比较 85, 84; 将 85 移到 H8中； vacant 是 H16.比较 69, 68; 将 69 移到 H16中；vacant 是 H32.比较 K 与 H32 的父结点，该结点为 69。K 小，继续，h = 1.比较 37, 36; 然后将 K 同 37 比较；K 小，将 37 移到 H32 中，并将K插入到 H64.（b）4329；（c）fixHeap做了12次比较，除了叶子外每一层次比较了2次。4.44证明：左边如果h为奇数，这时，所以；如果h为偶数，这时，但是h+1为奇数，所以为非整数，所以（说明：因为，且h为偶数，所以h的最小值为2，考虑函数。）综上所述，对于一切整数h，且

25、，有4.45假定希尔排序共分5个阶段，并且每一阶段的递增量为常数。再假定这5个递增量中的最大值为k，在最坏情况（倒序序列）下进行排序。在第一阶段将元素分成了k组，每一组大约为n/k个元素，这时对每一组进行直接插入排序，因为每一组元素的顺序也是倒序的，根据对最坏情况下直接插入排序的算法复杂度分析有，所以每一组的时间约为，k组总共的时间约为，由于k为常数，所以。同样道理，在其他阶段所用的时间不会多于第一阶段的时间，也就是不会超过的量级，但是总的时间复制度仍然是4.46如果m减半，基数radix取其平方数。因为。专心-专注-专业5.1 画出当n为4时，算法FindMax（算法1.3）的判定树。5.2

26、 5.3 我们以策论的观点分析了查找n个元素中最大元素和最小元素算法的下限。而如果以判定树的观点我们会得到什么样的下限呢？5.4 基于堆结构（4.8.1节）写一个查找max（最大元素）和secondLargest（第二大元素）的算法。a) 说明下述过程将max（最大元素）放置在E1中。序列E的索引为。heapFindMax(E,n) int last; Load n elements into En,E2*n-1. for (last=2*n-2; last>=2; last-=2) Elast/2 = max(Elast,Elast+1);for循环对元素 顺序赋值，并没有对任何数据进

27、行修改。使用归纳法证明调用函数heapFindMax后，每个位置的元素都是包含它在内的子树的最大值。对于最底层的叶子元素n到2n-1推论成立。现假设对所有位置大于k的元素该推论都成立，现考虑节点k。在对节点k赋值的时候，last为2k，这时位置k为其孩子2k和2k+1的最大值，而对于2k和2k+1，根据推论都是其子树的最大值，所以k为其子树的最大值。所以该推论成立，由此经过for循环后，E1中为最大值。b) 说明如何判断有那些元素输给了winner。对于每一个内部节点都是它孩子的一个拷贝，在为该节点赋值的时候，另一个孩子节点就是失败者。现假设所有键值都不相同，则从根节点开始到其某个叶节点有一条

28、道路，这条道路上的所有节点值都为max，在这条路上除叶节点之外，所有内节点的另一个孩子都是相对于max的失败者。c) 在heapFindMax后，继续完成查找secondLargest的算法。max = E1;secondLargest = ;i = 1;while (i < n) if (E2*i = max) i = 2*i;if (Ei+1 > secondLargest)secondLargest = Ei+1; else i = 2*i+1;if (Ei-1 > secondLargest)secondLargest = Ei-1; return secondLar

29、gest;5.5 给出通过竞争的策略查找第二大元素的平均比较次数。a) 当n为2的整数次幂。首先必须通过n-1次比较将最大元素排除，下面就是考虑相对于最大元素失败的元素最为候选的第二大元素的平均比较次数b) 当n不是2的整数次幂。提示：参考练习5.4。5.6 以下算法通过持续的扫描序列，并将最大的两个元素保存下来的方法，查找含有n个元素的序列E的最大元素和第二大元素。（这里假设）if (E1>E2) max = E1; second = E2;else max = E2; second = E1;for (i = 3; i<= n; i+) if (Ei > second)

30、second = max; max = Ei; else second = Ei;a) 该算法在最坏情况下要比较多少次？给出当n=6时的最坏情况。在最坏情况下的比较次数为次。最坏情况会在输入序列为逆序时发生。b) 给出在输入为n时，该算法的平均比较次数。在每次循环中比较次数为一次或两次，并且至少比较一次。只有在Ei为前i个元素中最大的两个的时候会比较两次，这时的概率为，而对于比较一次的概率为。另外，在进入循环之前还比较了一次。所以平均比较次数为：5.8 经过修改的快速排序可以查找n个元素中第k大的元素，并且在大多数情况下这时所需要的时间要比完全排序n个元素的时间少。a) 为完成上述思想，实现修

31、改后的快速算法findKth。该算法的核心思想是在递归的使用Quicksort时会将序列分成两段，而对于findKth则仅仅需要对其中的某一段进行查找就可以了。/* Precondition: */Element findKth(Element E, int first, int last, int k)Element ans;if (first = last)ans = Efirst;elseElement pivotElement = Efirst;Key pivot = pivotElement.key;int splitPoint = partition(E, pivot, first

32、, last);EsplitPoint = pivotElement;if (k < splitPoint)ans = findKth(E, first, splitPoint - 1, k);else if (k > splitPoint)ans = findKth(E, splitPoint + 1, last, k);elseans = pivotElement;return ans;b) 证明在使用findKth查找中间元素时，最坏情况为。在进行快速排序的时候，最坏情况为每次调用partition的时候只是分出一个元素来。如果输入序列为已排序的，则使用findKth查找中间

33、元素的调用为，这时会递归的使用和来调用findKth。其内部也会递归的使用该值调用partition。根据对快速排序的分析，对这至少有个元素进行快速排序，在最坏情况下的比较次数为的。所以，findKth在最坏情况下的比较次数也是的。c) 为计算该方法的平均运行时间，列出其计算的递归方程。设有n个元素，要查找的元素序号为k，则该算法平均运行时间的递归方程为： 该算法的运行时间同比较次数近似相同。为避免含有两个参数的递归方程，我们可以通过一个上限表达式来替代确切的递归方程式。设为当n个元素中k的位置为最坏情况式的平均比较次数，即为，所以：d) 分析你的算法的平均运行时间。给出渐进估计。根据上述的递

34、归方程，可以猜想，其中c为某一个确定的常数。为证明该假设，根据上述的简化的递归方程有：为保证该不等式成立，并取得适当的常数c，因为，则可取。5.10 假定使用如下算法查找n个元素中第k大的元素。Build a heap H out of the n keys;for (i=1; i<=k; i+)output(getMax(H);deleteMax(H);在k值取何值时，该算法的时间复杂度为线性的。在最坏情况下建堆需要次比较。如果在堆中含有m个元素，则使用FixHeap的DeleteMax大约需要次比较。因此，for循环大约需要进行次比较。则总的比较次数的下界为，取k值为，则总的时间还是

35、的。5.11 给出查找n个元素中第k大元素的算法（）。写出所有影响运行时间的执行细节，并给出该算法的时间复杂度描述，关于n和k的函数。5.12 假设n为偶数，其中间元素为第小的元素。对计算其平均时间复杂度的下限和定理5.3（其中假定n为奇数）进行必要的修改。无论n是奇数还是偶数都至少需要次“必要的”比较。策略论的策略是利用表5.4中的定义，其中S状态最多为，L状态最多为。根据表5.4中的定义，每一次比较最多产生一个L状态，也最多产生一个S状态，而策略论的任何算法都可以至少剔除次“非必要的”比较。这时修改后的定理5.3为：在n为偶数时，其中间元素为第小的元素。任何查找该中间元素的算法，在最坏情况

36、下至少需要次比较。5.14 给出在最坏情况下，通过6次比较查找出5个元素中的中间元素的算法。仅需要描述其步骤，不需要写出代码。如同在图5.2中那样使用树图描述该步骤。提示：可以参考5.6节中使用的策略以减少比较次数。任何大于其它三个元素的元素或这时任何小于其他三个元素的元素都应该被舍弃。为简化对该算法的描述，我们引入在练习4.56中使用的CEX（比较-交换）指令。CEX i,j 表示将下标为i和j的元素进行比较，并在需要的时候进行交换，以便使得值小的元素的下标也是小的。CEX 1,2 /比较1和2，将小值放在1中，大值放在2中；CEX 3,4 /比较3和4，将小值放在3中，大值放在4中；CEX

37、 1,3 /比较两个较小的元素1和3，将1，2，3，4中最小的方在1中；这时可以断定1中的元素 /要比其他三个元素小，可以将其舍弃。而经过比较后我们也知道了。CEX 2,5CEX 2,3 /经过这两次比较后，将剩余元素中最小的元素放在了2中；CEX 3,5 /经过这次比较交换，将剩余元素中最小的元素放在了3中，而此元素也是所有5个元素中/第三小的元素，也就是所求的中间元素。5.15 给出在最坏情况下仅比较7次就将5个元素的序列排序的算法。仅需要描述其步骤，不需要写出代码。如同在图5.2中那样使用树图描述该步骤。提示：可以参考5.6节中使用的策略以减少比较次数。根据上题中的比较过程，经过了6次比

38、较后确定了第一小元素在E1中，第二小的元素在E2中，第三小的元素在E3中，这时只要在增加一次比较CEX 4,5，就会将第四小的元素放在E4中，剩下的元素就是第五小的元素在E5中，这时也就是经过了7次比较将5个元素排序了。5.16 以策论的观点证明定理1.16（在已排序序列中搜索的时间下限）提示：定义一个含有待查找元素的有效序列段，段头为该段的最小元素，段尾为该段的最大元素。定理1.16：任何通过比较方式在含有n个元素，且已排序的序列中搜索指定元素K的算法，都至少需要次比较。假定序列E的下标为，在其中搜索键值K。按照策论的策略保持一个包含键值K的子段，其变量含义及初始化定义如下：（含有K的子段中

39、的最小元素下标，初始化为0。）（含有K的子段中的最大元素下标，初始化为n-1。）（含有K的子段的中间元素下标，初始化为。）（含有K子段的元素数目，初始化为n。）在每次更改L和H后都必须对M和R进行更新。假定我们进行的是三路比较（，>和<）。按照下述步骤更新L和H：1、如果，则说明，更新；2、如果，则说明，更新；3、如果，则说明，更新；4、如果，则说明，更新。在上述步骤中，可以得到。例如对步骤4有：如果该算法在之前停止，还是至少有两种情况的输出。例如，如果，则，这时或者是，或者是K不在序列中。现假定当时算法终止，根据上述递归式和初始条件，可以得到。因此有，又因为q为整数则。5.17

40、已知序列E的索引为（即E中包含n+1个元素）。现假定E为单峰的，就说存在某个索引值为M，对于小于索引M的元素是顺序递增的，而对于大于索引M的元素是顺序递减的。这时EM为最大值元素。（注意，M可以是0或者n）现在的问题就是找到这个M。a) 作为热身动作，说明当n2时，两次比较是必须的，并且是充分的。因为在3个元素中找到其中最大值，通过两次比较是必须的，而且是充分的。b) 写出通过比较E中的元素来查找M的算法。算法策略为找到序列中第一个逆序，则该逆序的第一个元素即为M。void getM(Element E) for( int i=0; i<E.length-1; i+) if Ei<

41、Ei+1 System.out.println(Ei); return; System.out.println(EE.length-1); return;c) 给出你的算法在最坏情况下的比较次数。（该算法应该是的）上述算法在最后元素为所查找元素的时候为最坏情况，比较次数为n次。d) 假定，即为第k个斐波纳契数，其中。给出经过次比较查找到M的算法，仅需要描述算法的步骤就可以，不需要给出详细的代码。已知条件：，；元素个数为；e) 给出策论的基本策略，说明任何通过比较方式查找M的算法至少需要次比较，其中。这说明该问题仅仅比搜索已排序序列的问题稍微复杂一点。提示：细化5.16中的策略。5.18 假设E

42、1和E2都是含有n个元素，并以升序排列的序列。a) 设计查找这2n个元素中第n小元素（该元素即为合并后集合的中间元素）的算法，限定该算法的复杂度为。为简单起见，可假设所有元素都是不等的。定理4.4 任何通过比较将两个都含有n/2个元素的已排序序列合并为一个排序序列的算法，在最坏情况下至少需要比较n-1次比较。而在一个已排序序列中查找第k小的元素的时间为的。所以在先排序，再查找的策略下解决该问题的时间为O(n)的。b) 给出该问题的时间下界。5.19 a) 给出判断含有n个元素的序列中所有元素是否都是互不相同的算法。假设有三种比较方式，也就是说比较两个元素的结果可能是<、=或>。说明

43、该算法共比较了多少次。将n个元素排序是的，并且在排序的时候在遇到有相等情况的时候会自动的停止排序或报告该信息。如果在排序的过程中没有出现相等的情况，则说明该序列中所有的元素都是互不相同的。（所有相邻的元素在最后一次排序时都要直接进行比较，否则算法不能确定序列已经被排序了。）所以总的时间是的。如果在使用排序算法的时候考虑到了相等的情况，则对已经排序过的序列判断其中是否有相同的键，只需要扫描一遍就可以了，所用的时间也是的。所以总的时间还是的。b) 给出所需比较次数的下限。（试一试）考虑序列中的所有元素都是互不相同的。假定排序后元素为。算法只有在获取了相邻元素和的相对关系后，才具有用于排序的足够信息

44、。假定存在两个元素和，算法并没有获取关于它们的相对位置的信息。这时，算法并没有足够的信息确定，因为这些元素同序列中其他元素的比较不能提供这样的信息。这时，该算法声明该序列中有两个相等的元素的结论是错误的。这时，如果该算法声明该序列中所有元素都是互不相同的，则只需要更改，使其等于，这时的更改对其他的比较结果是没有影响的，所以算法给出了一个错误的结论。因此，为判断序列中没有相等的元素，算法也必须像排序那样收集到足够的信息才可以。这时看来虽然时间下限都是的，但是三路（，<和>）比较相对与两路（<和>）对于解决该问题更加有效。但是如果序列中的所有元素都是互不相同的，则对于“”的

45、比较并不会提供任何有用的信息。所以在最坏情况下，对n个元素进行排序还是需要的，因此确定序列中是否有相同元素所需要的比较次数，在最坏情况下仍然是的。5.20 考虑判定长度为n的位串是否含有两个连续0的子串的问题。基本的操作方式是检测位串的每一个位置，看该位置是0还是1。对于给出算法。boolean getTwo0( Bit E) count = 2;for (i=0; i<E.length; i+) if (Ei = 0) count-; else count = 2; if (count = 0) return ture; else return false; 5.21 假设你的计算机内

46、存很小，并且还有一个包含顺序键值元素的外部文件（或者在磁盘上，或者在磁带上）。键值可以被读到内存中处理，但是每一个键值只可读一次。a) 为查找该外部文件中键值最大的一个，最少需要多少的内存存储单元？给出证明。算法需要至少两个存储单元，一个用于存储max，另一个用于存储next。将读入的第一个元素放入max中，然后每次都将下一个元素放入next中，然后将其同max进行比较，如果，则将该元素放入到max中；否则读取下一个元素。为解决该问题不可能再减少存储单元的数目了，如果仅使用一个存储单元，那么连比较都进行不了。b) 如果是查找中间元素呢？为简便起见可以假设n为奇数，这时中间元素为，这时只需要个存

47、储空间就可以解决该问题了。算法的策略是按照插入排序的方法，每次从外部文件中读取一个元素，并将其插入到前面已排序序列中，当然对已排序序列只保存其前个元素，还需要一个存储单元用于存储当前读入的键值，所以共需要个存储单元。现在证明为解决该问题不可能再减少存储空间的数目了，现假定存在某种算法，该算法使用更少的存储空间来查找中间元素。现在要说明的是这样的算法会输出错误的结果。（对于的问题，只要证明就可以了。）在该算法选择查找结果的时候，它会读入某一个外部元素，并覆盖掉以前读入的某一个元素，可以将被覆盖的元素称作被排除的元素，因为根据问题中的条件它是不可能作为该算法的输出了。这时，根据策论的方式，我们可以

48、使得该元素即为中间元素。假定第一个被覆盖的元素为序列中第i小的元素，当将其排除在外的时候，至少还有个元素还没有同它比较，同时假定在这些剩余元素中还有个元素要比该被排除的元素小。则综合所有比该元素小的元素个数为个，这时该被排除的元素即为中间元素。5.22 a) 已知有n个元素和某一整数k（）。给出一个可以查找到任何一个第k小元素的高效算法。（例如，如果，该算法可以给出第一小、第二小或第三小的元素。其中不需要知道输出元素的确切位置。）给出该算法的比较次数。提示：不要试图寻找复杂的方法。给出一种短小，简单的算法。在n个元素中查找到小于Ek的元素的算法需要次比较。b) 给出解决该问题的比较次数的下限，

49、是关于n和k的一个函数。为集合中的每一个元素分配一个权值w(x)。1、初始化所有键值，设置；2、比较Ei和Ej，且，则更新；3、比较Ei和Ej，且，则更新；4、比较Ei和Ej，且，则更新；5、比较Ei和Ej，且，则重复上述步骤，不进行更新。经过上述的步骤，只有权为0的元素是在某次比较中获胜的一方。由于在上述的步骤中没有为各个元素上的权加入新的值，所以总的权数为n。可以按照在证明定理5.2时那样建立一个树来分析这个过程。在比较的过程中，每一棵树的根都是该树中最小的元素，要合并两个树，只需要比较它们的根元素，将失败的元素作为新树的根，然后将这两棵树分别作为它的左右子树。但是，无论何时，如果树根为i

50、，这w(i)的值代表了该树中的节点数。也就是说，这个根元素将其他w(i)-1个元素的权都赢了过来，在加上它自己本身的权值1，也就是该树的节点数。这时，如果要查找小于K的元素，就需要在算法执行到中间的某一时刻停止。当所有没有元素的权时，如果在这时停止该算法，则任何的输出结果都是不对的。可以假设Ek在某一棵树上，而根据已知条件，没有树的节点超过n-k，也就说不能确定在其他树上的节点是否都小于节点Ek。因此，算法应该在只有一个键的权为n-k+1时，输出剩余的元素即为所求。因为这时已经有n-k+1个节点已经被提取出来了，也就是所求。而有n-k+1个节点的树，有n-k条边，每条边是比较一次的结果，就是说

51、解决该问题的比较次数下限为n-k。5.23 设E为含有n个元素的正整数序列。E中的“大半元素”是在这含有n个元素的序列中出现次数为次以上的元素。“大半元素”问题就是如果存在这样的元素，则输出该元素；如果这样的元素不存在，则输出-1。解决该问题的操作仅为比较E中的元素，并做适当的移动和拷贝。给出解决该问题的一个算法。分析在最坏情况下该算法的时间和空间复杂度。（实现的复杂度是简单的，但是该问题有一个线性的解决方案。提示：使用在5.3.2节中使用的设置变量的技术。）为简单起见，设n为偶数。设节点信息为（键值，相等数），将这n个元素两两比较，规则如下：1、 为每一个元素中的“相等数”初始化为1；2、

52、将最底层的n个元素两两比较，如果左右儿子的元素相等，则新建节点的“键值”为左儿子，“相等数”为左右儿子“相等数”之和；否则，新节点的“键值”可以左右儿子的任意一个，这里假设为较大的那一个，“相等数”为1；同时，记录“相等数”最大的那个节点的信息。3、 顺序按层两两比较，处理方法同2；4、 这样经过n-1次比较后，就选出了这n个元素中的最大值，同时也得到了“相等数”最大的那个节点的信息，设为M；5、 如果M.相等数>2，则以该节点的元素值同序列中的所有元素进行相等比较，并记录相等计数，如果该计数大于n/2，则输出该元素；否则，直接输出-1。5.24 设M为一个的整数矩阵，其中每一行的元素是

53、递增的（从左至右），每一列的元素是递增的（从上至下）。考虑这样的一个问题，判定整数x在M中的位置，或者确定x不在M中。以策论的观点给出解决该问题的比较次数的下限。该算法允许以三种方式比较x和Mij，比较结果为。注意：解决该问题的高效算法为第四章的习题4.58。如果算法设计和策论观点足够的好，则该算法的比较次数同该算法的下限是相同的。6.1 在需要扩大序列时，所使用的策略是两倍复制当前序列。现在要使用四倍来复制当前序列，评估这种策略的时间和空间耗费。假定在有向序列中插入第（n+1）个元素的时候，触发了双倍复制序列操作。设当从旧序列中复制一个元素到新序列时的时间消耗为t（在这里设定t为某一固定值）

54、。则在将旧序列复制到新序列的时候需要进行n次传输操作。而这次在前一次双倍复制操作已经进行了次传输，再前次是，并以此类推。则总的时间消耗为。如果使用四倍复制策略，则总的时间消耗为，即。对于空间消耗，四倍复制策略会分配所需求空间总量的四倍，而两倍复制策略会分配所需求空间总量的两倍。6.2 为保存栈的空间，在被分配的存储空间存在片断的时候会进行适当的收缩。这可以作为对双倍数组负责策略的补充。假设在栈大小超出已分配空间大小的时候，所使用的分配策略为双倍复制。使用“已摊销成本”方式，评估以下收缩策略。每次操作是否消耗固定的“已摊销成本”的时间a) 如果pop操作后栈元素数少于时，收缩栈的大小为。在最坏情况下的时间复杂度为的。假定栈大小为，当前栈中已经有n个元素（大小为）。这时如果连续执行两次push操作就会触发双倍复制动作，所需要的时间为，栈大小变为。现在