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

《《计算机算法-设计与分析导论》课后习题答案复习课程.doc》由会员分享，可在线阅读，更多相关《《计算机算法-设计与分析导论》课后习题答案复习课程.doc（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析第四章 排序姓 名：王 强 学号：205093454.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最后一个元素交换。这时，max元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max已经不在未排序序列之中了。重复上述过程直到完成整个序列的排序。(a) 写出Maxsort算法。其中待排序序列为E，含有n个元素，脚标为范围为。void Maxsort(Element E) int maxID = 0; for (int i=E.lengt

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

3、况为已排序，需要(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)反正法：假设当没有一对相邻的元素需要交换位置的时候，得到的序列是未排序的，则该未排序队列至少存在一对元素是逆序的，现设这

4、两个元素未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)0) numPairs = last; last = -1; for(int j=0; jEj+1) Interchange Ej and Ej+1; last = j; return;(c) 这种改进对最坏情况并没有什么改进，因为在最坏情况（倒序）时，还时从

5、n-1到1的每个过程都循环一遍。4.5不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同时相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。4.61,n,n-1,2 和 n,n-1,3,1,2 说明：将1放在n2的逆序中任何位置都不改变最坏情况。4.7插入排序的最佳情况是序列已排序，这时候需要比较次数为n-1次，移动次数为0次。4.8(a) 最坏情况为插入位置在正数第2个位置，或者倒数第2

6、个位置，比较次数i/2。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。(b) 在最坏情况下插入位置在第1个位置上，移动次数为i次。(c) 由于折半插入排序只是减少了比较的次数，并没有减少移动的次数，所以算法的时间复杂度仍然是的。(d) 采用链表数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-1)。但是这样也仅仅是减少了元素的移动时间，并没有减少元素的比较次数，所以算法的时间复制度仍然是的。4.9首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均时间复制度会有所增加，因为在寻找插入位置

7、的时候，会多比较那些相等的值。4.10含有n个元素的逆排序序列的逆序数为。4.11IntList listInsSort(IntList 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已

8、经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为的，平均情况和最坏情况的时间消耗为的。调用insertl时，变量k的变化范围为0n-1的。因此在整个过程中的时间复制度，最好为，平均和最坏为4.124.13extendSmallRegion的后置条件为：在元素Elow,.,EhighVac-1中最左面一个“枢纽”的元素将被移动到EhighVac中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。4.15对于已经排序的序列，进行快速排序将会进行次比较和次移动。Efirst被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。

9、4.17考虑含有k个元素的一个子区域。选择“枢纽”需要3（）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总共需要进行k次的比较。这相对于简单的选择Efirst作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择Efirst 、E(first+last)/2和Elast的时候，总是选中了两个序列中最小的两个元素，这样每次都选中序列中第二小的元素做“枢纽”的话，总的比较次数是次。所以说对于逆序输入的序列进行快速排序，如果采用选择Efirst 、E(first+last)/2和Elast的中间元素作为“枢纽”的方法的时间复制度仍然是的。4.19(a) 在第一次调用

10、后序列为：1，9，8，7，6，5，4，3，2，10；移动1次。在第二次调用后序列不变，没有移动。对含有n个元素的逆序序列进行排序，调用partition的总的移动次数为，同时还需要加上在选择“枢纽”是用到的次移动。(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

11、中，partitionL需要做90（109）次移动，而partition仅仅做了5（10/2）次移动。（另外完成快速排序还需要增加选择“枢纽”是用到的18次移动。4.21（a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动，概率为。所以对k个元素进行排序的平均移动次数为。因此使用partitionL的快速排序的移动次数大约为。（b）在partition中，每个 “unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”枢

12、纽元素的时候需要移动，概率为；在extendLargeRegion中，“unknown”元素在“小于”枢纽元素的时候需要移动，概率为。所以平均的移动次数为。因此使用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);

13、 int e2 = first(in2); IntList remMerged; if (e1 = e2) remMerged = 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

14、: first(in1) = first(in2) ? cons(first(in1), listMerge(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，m-1)；所以P（k，m）P（k-1，m）P（k，m-1），。方案2：在输出序列中共有m+k个位置，如果第一个序列中的k个元素在输出序列中的位置已经确定，则只需要将第二个序列中的m个元素顺序输出到输出序列中空缺的m个位置中就可以了。所以选

15、择这k个位置的输出序列以二叉树表示，分别需要的选择方案为。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(Elem

16、ent in, Element out, 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）由于输入序列和输出序列为不

17、同的区域，所以现在merge在每次比较的时候都需要一次移动。所以对于mergesort来说，移动次数将是。而对于快速排序，平均移动次数为4.29对于深度为（D-1）的递归树共有个叶子结点，其中有个叶子可以有两个孩子，所以在深度为D的递归树中有个叶子。因此，即。4.31=2; last-=2) Elast/2 = max(Elast,Elast+1);for循环对元素 顺序赋值，并没有对任何数据进行修改。使用归纳法证明调用函数heapFindMax后，每个位置的元素都是包含它在内的子树的最大值。对于最底层的叶子元素n到2n-1推论成立。现假设对所有位置大于k的元素该推论都成立，现考虑节点k。在对

18、节点k赋值的时候，last为2k，这时位置k为其孩子2k和2k+1的最大值，而对于2k和2k+1，根据推论都是其子树的最大值，所以k为其子树的最大值。所以该推论成立，由此经过for循环后，E1中为最大值。b) 说明如何判断有那些元素输给了winner。对于每一个内部节点都是它孩子的一个拷贝，在为该节点赋值的时候，另一个孩子节点就是失败者。现假设所有键值都不相同，则从根节点开始到其某个叶节点有一条道路，这条道路上的所有节点值都为max，在这条路上除叶节点之外，所有内节点的另一个孩子都是相对于max的失败者。c) 在heapFindMax后，继续完成查找secondLargest的算法。max =

19、 E1;secondLargest = ;i = 1;while (i secondLargest)secondLargest = Ei+1; else i = 2*i+1;if (Ei-1 secondLargest)secondLargest = Ei-1; return secondLargest;5.5 给出通过竞争的策略查找第二大元素的平均比较次数。a) 当n为2的整数次幂。首先必须通过n-1次比较将最大元素排除，下面就是考虑相对于最大元素失败的元素最为候选的第二大元素的平均比较次数b) 当n不是2的整数次幂。提示：参考练习5.4。5.6 以下算法通过持续的扫描序列，并将最大的两个元

20、素保存下来的方法，查找含有n个元素的序列E的最大元素和第二大元素。（这里假设）if (E1E2) max = E1; second = E2;else max = E2; second = E1;for (i = 3; i second) second = max; max = Ei; else second = Ei;a) 该算法在最坏情况下要比较多少次？给出当n=6时的最坏情况。在最坏情况下的比较次数为次。最坏情况会在输入序列为逆序时发生。b) 给出在输入为n时，该算法的平均比较次数。在每次循环中比较次数为一次或两次，并且至少比较一次。只有在Ei为前i个元素中最大的两个的时候会比较两次，这

21、时的概率为，而对于比较一次的概率为。另外，在进入循环之前还比较了一次。所以平均比较次数为：5.8 经过修改的快速排序可以查找n个元素中第k大的元素，并且在大多数情况下这时所需要的时间要比完全排序n个元素的时间少。a) 为完成上述思想，实现修改后的快速算法findKth。该算法的核心思想是在递归的使用Quicksort时会将序列分成两段，而对于findKth则仅仅需要对其中的某一段进行查找就可以了。/* Precondition: */Element findKth(Element E, int first, int last, int k)Element ans;if (first = las

22、t)ans = Efirst;elseElement pivotElement = Efirst;Key pivot = pivotElement.key;int splitPoint = partition(E, pivot, first, last);EsplitPoint = pivotElement;if (k splitPoint)ans = findKth(E, splitPoint + 1, last, k);elseans = pivotElement;return ans;b) 证明在使用findKth查找中间元素时，最坏情况为。在进行快速排序的时候，最坏情况为每次调用par

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

24、式的平均比较次数，即为，所以：d) 分析你的算法的平均运行时间。给出渐进估计。根据上述的递归方程，可以猜想，其中c为某一个确定的常数。为证明该假设，根据上述的简化的递归方程有：为保证该不等式成立，并取得适当的常数c，因为，则可取。5.10 假定使用如下算法查找n个元素中第k大的元素。Build a heap H out of the n keys;for (i=1; i和）。按照下述步骤更新L和H：1、如果，则说明，更新；2、如果，则说明，更新；3、如果，则说明，更新；4、如果，则说明，更新。在上述步骤中，可以得到。例如对步骤4有：如果该算法在之前停止，还是至少有两种情况的输出。例如，如果，则

25、，这时或者是，或者是K不在序列中。现假定当时算法终止，根据上述递归式和初始条件，可以得到。因此有，又因为q为整数则。5.17 已知序列E的索引为（即E中包含n+1个元素）。现假定E为单峰的，就说存在某个索引值为M，对于小于索引M的元素是顺序递增的，而对于大于索引M的元素是顺序递减的。这时EM为最大值元素。（注意，M可以是0或者n）现在的问题就是找到这个M。a) 作为热身动作，说明当n2时，两次比较是必须的，并且是充分的。因为在3个元素中找到其中最大值，通过两次比较是必须的，而且是充分的。b) 写出通过比较E中的元素来查找M的算法。算法策略为找到序列中第一个逆序，则该逆序的第一个元素即为M。vo

26、id getM(Element E) for( int i=0; iE.length-1; i+) if EiEi+1 System.out.println(Ei); return; System.out.println(EE.length-1); return;c) 给出你的算法在最坏情况下的比较次数。（该算法应该是的）上述算法在最后元素为所查找元素的时候为最坏情况，比较次数为n次。d) 假定，即为第k个斐波纳契数，其中。给出经过次比较查找到M的算法，仅需要描述算法的步骤就可以，不需要给出详细的代码。已知条件：，；元素个数为；e) 给出策论的基本策略，说明任何通过比较方式查找M的算法至少需要

27、次比较，其中。这说明该问题仅仅比搜索已排序序列的问题稍微复杂一点。提示：细化5.16中的策略。5.18 假设E1和E2都是含有n个元素，并以升序排列的序列。a) 设计查找这2n个元素中第n小元素（该元素即为合并后集合的中间元素）的算法，限定该算法的复杂度为。为简单起见，可假设所有元素都是不等的。定理4.4 任何通过比较将两个都含有n/2个元素的已排序序列合并为一个排序序列的算法，在最坏情况下至少需要比较n-1次比较。而在一个已排序序列中查找第k小的元素的时间为的。所以在先排序，再查找的策略下解决该问题的时间为O(n)的。b) 给出该问题的时间下界。5.19 a) 给出判断含有n个元素的序列中所

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

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

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

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

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