《算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
与分析》课后习题 4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最后一个元素交换。这时，max元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max已经不在未排序序列之中了。重复上述过程直到完成整个序列的排序。 (a) 写出Maxsort算法。其中待排序序列为E，含有n个元素，脚标为范围为 。 void Maxsort(Element[] E) { int maxID = 0; for (int i=E.length; i>1; i--) { for (int j=0; j
E[maxID]) maxID = k; } E[i] <--> E[maxID]; } } (b) 说明在最坏情况下和平均情况下上述算法的比较次数。 最坏情况同平均情况是相同的都是 。 4.2：在以下的几个练习中我们研究一种叫做“冒泡排序”的排序算法。该算法通过连续几遍浏览序列实现。排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；以此类推。 (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)反正法：假设当没有一对相邻的元素需要交换位置的时候，得到的序列是未排序的，则该未排序队列至少存在一对元素是逆序的，现设这两个元素未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)0) { numPairs = last; last = -1; for(int j=0; jE[j+1]) { Interchange E[j] and E[j+1]; last = j; } } } return; } (c) 这种改进对最坏情况并没有什么改进，因为在最坏情况（倒序）时，还时从n-1到1的每个过程都循环一遍。 4.5 不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同时相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。 4.6 1,n,n-1,…,2 和 n,n-1,…,3,1,2 说明：将1放在n～2的逆序中任何位置都不改变最坏情况。 4.7 插入排序的最佳情况是序列已排序，这时候需要比较次数为n-1次，移动次数为0次。 4.8 (a) 最坏情况为插入位置在正数第2个位置，或者倒数第2个位置，比较次数[i/2]。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。 (b) 在最坏情况下插入位置在第1个位置上，移动次数为i次。 (c) 由于折半插入排序只是减少了比较的次数，并没有减少移动的次数，所以算法的时间复杂度仍然是 的。 (d) 采用链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-1)。但是这样也仅仅是减少了元素的移动时间，并没有减少元素的比较次数，所以算法的时间复制度仍然是 的。 4.9 首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均时间复制度会有所增加，因为在寻找插入位置的时候，会多比较那些相等的值。 4.10 含有n个元素的逆排序序列的逆序数为 。 4.11 IntList 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已经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为 的，平均情况和最坏情况的时间消耗为 的。调用insertl时，变量k的变化范围为0～n-1的。因此在整个过程中的时间复制度，最好为 ，平均和最坏为 4.12 4.13 extendSmallRegion的后置条件为：在元素E[low],...,E[highVac-1]中最左面一个≥“枢纽”的元素将被移动到E[highVac]中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。 4.15 对于已经排序的序列，进行快速排序将会进行 次比较和 次移动。E[first]被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。 4.17 考虑含有k个元素的一个子区域。选择“枢纽”需要3（ ）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总共需要进行k次的比较。这相对于简单的选择E[first]作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择E[first] 、E[(first+last)/2]和E[last]的时候，总是选中了两个序列中最小的两个元素，这样每次都选中序列中第二小的元素做“枢纽”的话，总的比较次数是 次。所以说对于逆序输入的序列进行快速排序，如果采用选择E[first] 、E[(first+last)/2]和E[last]的中间元素作为“枢纽”的方法的时间复制度仍然是 的。 4.19 (a) 在第一次调用后序列为：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中，partitionL需要做90（10×9）次移动，而partition仅仅做了5（10/2）次移动。（另外完成快速排序还需要增加选择“枢纽”是用到的18次移动。 4.21 （a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动，概率为 。所以对k个元素进行排序的平均移动次数为 。因此使用partitionL的快速排序的移动次数大约为 。 （b）在partition中，，每个 “unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”枢纽元素的时候需要移动，概率为 ；在extendLargeRegion中，“unknown”元素在“小于”枢纽元素的时候需要移动，概率为 。所以平均的移动次数为 。因此使用partition的快速排序的移动次数大约为 （c）使用partition的快速排序将使用 次比较和 次移动。归并排序的时间复制度大约是 。 4.23 IntList 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) { 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 : 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个元素的交换数，其中n＝k＋m。则： If A[0] < B[0] then 调用P(k-1，m)； If A[0] > B[0] then 调用P(k，m-1)； 所以P（k，m）＝P（k-1，m）＋P（k，m-1）， 。 方案2：在输出序列中共有m+k个位置，如果第一个序列中的k个元素在输出序列中的位置已经确定，则只需要将第二个序列中的m个元素顺序输出到输出序列中空缺的m个位置中就可以了。所以选择这k个位置的输出序列以二叉树表示，分别需要的选择方案为 。 4.26 如果输入序列是已排序的，这合并两个子序列需要 次比较就可以了。递归表示为： ，如果n是2的整数次幂，则 ，如果使得 ，则 。 4.27 （a）修改算法Mergesort，增加一个工作序列的参数。在Mergesort之上添加mergeSortWrap，用于初始工作序列： mergeSortWrap(Element[] E, int first, int last) { Element[] W = new Element[E.length]; mergeSort(E, E, W, first, last); } 修改后的Mergesort为： mergeSort(Element[] in, Element[] out, Element[] work, int first, int last) { if (first == last) if (in != out) out[first] = in[first]; 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在每次比较的时候都需要一次移动。所以对于mergesort来说，移动次数将是 。而对于快速排序，平均移动次数为 4.29 对于深度为（D-1）的递归树共有 个叶子结点，其中有 个叶子可以有两个孩子，所以在深度为D的递归树中有 个叶子。因此， ，即 。 4.31 4.34 这不是大顶堆，因为5小于它的右孩子7。 4.35 “COMPLEXITY”初始化为大顶堆后为“YTXPOEMICL” ，比较次数为14次（2+1+2+2+1+2+2+2）。 4.37 (a) 共需要9次； (b) 因为待排序序列已经是降序的，所以在初始建堆时，每次调用FixHeap仅做一次或两次比较就可以了，并且不会有元素的移动。因为堆结构所使用的二叉树为“左完全二叉树”，所以有如下已知条件：1、如果已知有n个结点，则该二叉树有n-1条边。现分条件说明初始建堆时的比较次数： 1、如果n为偶数，则最后一个内部结点只有一个左儿子，该结点仅需要一次比较；这时有两个孩子的结点个数为 （根据已知条件1），这些结点需要两次比较。所以总的比较次数为 次。 2、如果n为奇数，则所有内部结点都有两个孩子，这些结点都需要两次比较，则总的比较次数为 次。 综合1和2，当n为正整数时，总的比较次数为n-1次。 (c) 对算法4.7（初建堆）来说是最好的情况，因为只需要n-1次比较，没有元素的移动。 4.40 在推出for循环后，应该附加条件E[1]E[2]（交换E[1]和E[2]）。这种改变仅仅是减少了在调用FixHeap时的过顶处理，并没有减少比较次数。 4.42（a） K = H[100] = 1。将100从H[1]中移出； 开始fixHeapFast，vacant = 1 h = 6。 比较 99, 98; 将 99 移到 H[1]中；vacant 是 H[2]； 比较 97, 96; 将 97 移到 H[2] 中；vacant 是 H[4]； 比较 93, 92; 将 93 移到 H[4] 中；vacant 是 H[8]； 比较 K 与 H[8] 的父结点，该结点为 93。 K 小，继续，h = 3. 比较 85, 84; 将 85 移到 H[8]中； vacant 是 H[16]. 比较 69, 68; 将 69 移到 H[16]中；vacant 是 H[32]. 比较 K 与 H[32] 的父结点，该结点为 69。 K 小，继续，h = 1. 比较 37, 36; 然后将 K 同 37 比较； K 小，将 37 移到 H[32] 中，并将K插入到 H[64]. （b）4＋3＋2＝9； （c）fixHeap做了12次比较，除了叶子外每一层次比较了2次。 4.44 证明： 左边＝ 如果h为奇数，这时 ，所以 ； 如果h为偶数，这时 ，但是h+1为奇数，所以 为非整数，所以 （说明：因为 ，且h为偶数，所以h的最小值为2，考虑函数 。） 综上所述，对于一切整数h，且 ，有 4.45 假定希尔排序共分5个阶段，并且每一阶段的递增量为常数。再假定这5个递增量中的最大值为k，在最坏情况（倒序序列）下进行排序。在第一阶段将元素分成了k组，每一组大约为n/k个元素，这时对每一组进行直接插入排序，因为每一组元素的顺序也是倒序的，根据对最坏情况下直接插入排序的算法复杂度分析有 ，所以每一组的时间约为 ，k组总共的时间约为 ，由于k为常数，所以 。同样道理，在其他阶段所用的时间不会多于第一阶段的时间，也就是不会超过 的量级，但是总的时间复制度仍然是 4.46 如果m减半，基数radix取其平方数。因为 。 5.1 画出当n为4时，算法FindMax（算法1.3）的判定树。 5.2 5.3 我们以策论的观点分析了查找n个元素中最大元素和最小元素算法的下限。而如果以判定树的观点我们会得到什么样的下限呢？ 5.4 基于堆结构（4.8.1节）写一个查找max（最大元素）和secondLargest（第二大元素）的算法。 a) 说明下述过程将max（最大元素）放置在E[1]中。序列E的索引为 。 heapFindMax(E,n) int last; Load n elements into E[n],…,E[2*n-1]. for (last=2*n-2; last>=2; last-=2) E[last/2] = max(E[last],E[last+1]); for循环对元素 顺序赋值，并没有对任何数据进行修改。使用归纳法证明调用函数heapFindMax后，每个位置的元素都是包含它在内的子树的最大值。对于最底层的叶子元素n到2n-1推论成立。现假设对所有位置大于k的元素该推论都成立，现考虑节点k。在对节点k赋值的时候，last为2k，这时位置k为其孩子2k和2k+1的最大值，而对于2k和2k+1，根据推论都是其子树的最大值，所以k为其子树的最大值。所以该推论成立，由此经过for循环后，E[1]中为最大值。 b) 说明如何判断有那些元素输给了winner。 对于每一个内部节点都是它孩子的一个拷贝，在为该节点赋值的时候，另一个孩子节点就是失败者。现假设所有键值都不相同，则从根节点开始到其某个叶节点有一条道路，这条道路上的所有节点值都为max，在这条路上除叶节点之外，所有内节点的另一个孩子都是相对于max的失败者。 c) 在heapFindMax后，继续完成查找secondLargest的算法。 max = E[1]; secondLargest = ; i = 1; while (i < n) { if (E[2*i] == max) { i = 2*i; if (E[i+1] > secondLargest) secondLargest = E[i+1]; } else { i = 2*i+1; if (E[i-1] > secondLargest) secondLargest = E[i-1]; } } return secondLargest; 5.5 给出通过竞争的策略查找第二大元素的平均比较次数。 a) 当n为2的整数次幂。 首先必须通过n-1次比较将最大元素排除，下面就是考虑相对于最大元素失败的元素最为候选的第二大元素的平均比较次数 b) 当n不是2的整数次幂。提示：参考练习5.4。 5.6 以下算法通过持续的扫描序列，并将最大的两个元素保存下来的方法，查找含有n个元素的序列E的最大元素和第二大元素。（这里假设 ） if (E[1]>E[2]) max = E[1]; second = E[2]; else max = E[2]; second = E[1]; for (i = 3; i<= n; i++) if (E[i] > second) second = max; max = E[i]; else second = E[i]; a) 该算法在最坏情况下要比较多少次？给出当n=6时的最坏情况。 在最坏情况下的比较次数为 次。最坏情况会在输入序列为逆序时发生。 b) 给出在输入为n时，该算法的平均比较次数。 在每次循环中比较次数为一次或两次，并且至少比较一次。只有在E[i]为前i个元素中最大的两个的时候会比较两次，这时的概率为 ，而对于比较一次的概率为 。另外，在进入循环之前还比较了一次。所以平均比较次数为： 5.8 经过修改的快速排序可以查找n个元素中第k大的元素，并且在大多数情况下这时所需要的时间要比完全排序n个元素的时间少。 a) 为完成上述思想，实现修改后的快速算法findKth。 该算法的核心思想是在递归的使用Quicksort时会将序列分成两段，而对于findKth则仅仅需要对其中的某一段进行查找就可以了。 /** Precondition: */ Element findKth(Element[] E, int first, int last, int k) Element ans; if (first == last) ans = E[first]; else Element pivotElement = E[first]; Key pivot = pivotElement.key; int splitPoint = partition(E, pivot, first, last); E[splitPoint] = pivotElement; if (k < splitPoint) ans = findKth(E, first, splitPoint - 1, k); else if (k > splitPoint) ans = findKth(E, splitPoint + 1, last, k); else ans = pivotElement; return ans; b) 证明在使用findKth查找中间元素时，最坏情况为 。 在进行快速排序的时候，最坏情况为每次调用partition的时候只是分出一个元素来。如果输入序列为已排序的，则使用findKth查找中间元素的调用为 ，这时会递归的使用 和 来调用findKth。其内部也会递归的使用该值调用partition。根据对快速排序的分析，对这至少有 个元素进行快速排序，在最坏情况下的比较次数为 的。所以，findKth在最坏情况下的比较次数也是 的。 c) 为计算该方法的平均运行时间，列出其计算的递归方程。 设有n个元素，要查找的元素序号为k，则该算法平均运行时间的递归方程为： 该算法的运行时间同比较次数近似相同。为避免含有两个参数的递归方程，我们可以通过一个上限表达式来替代确切的递归方程式。设 为当n个元素中k的位置为最坏情况式的平均比较次数，即为 ，所以： d) 分析你的算法的平均运行时间。给出渐进估计。 根据上述的递归方程，可以猜想 ，其中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值为 ，则总的时间还是 的。 5.11 给出查找n个元素中第k大元素的算法（ ）。写出所有影响运行时间的执行细节，并给出该算法的时间复杂度描述，关于n和k的函数。 5.12 假设n为偶数，其中间元素为第 小的元素。对计算其平均时间复杂度的下限和定理5.3（其中假定n为奇数）进行必要的修改。 无论n是奇数还是偶数都至少需要 次“必要的”比较。策略论的策略是利用表5.4中的定义，其中S状态最多为 ，L状态最多为 。根据表5.4中的定义，每一次比较最多产生一个L状态，也最多产生一个S状态，而策略论的任何算法都可以至少剔除 次“非必要的”比较。这时修改后的定理5.3为：在n为偶数时，其中间元素为第 小的元素。任何查找该中间元素的算法，在最坏情况下至少需要 次比较。 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 1,3 //比较两个较小的元素1和3，将1，2，3，4中最小的方在1中；这时可以断定1中的元素 //要比其他三个元素小，可以将其舍弃。而经过比较后我们也知道了 。 CEX 2,5 CEX 2,3 //经过这两次比较后，将剩余元素中最小的元素放在了2中； CEX 3,5 //经过这次比较交换，将剩余元素中最小的元素放在了3中，而此元素也是所有5个元素中 //第三小的元素，也就是所求的中间元素。 5.15 给出在最坏情况下仅比较7次就将5个元素的序列排序的算法。仅需要描述其步骤，不需要写出代码。如同在图5.2中那样使用树图描述该步骤。提示：可以参考5.6节中使用的策略以减少比较次数。 根据上题中的比较过程，经过了6次比较后确定了第一小元素在E[1]中，第二小的元素在E[2]中，第三小的元素在E[3]中，这时只要在增加一次比较CEX 4,5，就会将第四小的元素放在E[4]中，剩下的元素就是第五小的元素在E[5]中，这时也就是经过了7次比较将5个元素排序了。 5.16 以策论的观点证明定理1.16（在已排序序列中搜索的时间下限）提示：定义一个含有待查找元素的有效序列段，段头为该段的最小元素，段尾为该段的最大元素。 定理1.16：任何通过比较方式在含有n个元素，且已排序的序列中搜索指定元素K的算法，都至少需要 次比较。 假定序列E的下标为 ，在其中搜索键值K。按照策论的策略保持一个包含键值K的子段，其变量含义及初始化定义如下： （含有K的子段中的最小元素下标，初始化为0。） （含有K的子段中的最大元素下标，初始化为n-1。） （含有K的子段的中间元素下标， ，初始化为 。） （含有K子段的元素数目，初始化为n。） 在每次更改L和H后都必须对M和R进行更新。假定我们进行的是三路比较（＝，>和<）。按照下述步骤更新L和H： 1、如果 ，则说明 ，更新 ； 2、如果 ，则说明 ，更新 ； 3、如果 ，则说明 ，更新 ； 4、如果 ，则说明 ，更新 。 在上述步骤中，可以得到 。例如对步骤4有： 如果该算法在 之前停止，还是至少有两种情况的输出。例如，如果 ，则 ，这时或者是 ，或者是K不在序列中。 现假定当 时算法终止，根据上述递归式和初始条件 ，可以得到 。因此有 ，又因为q为整数则 。 5.17 已知序列E的索引为 （即E中包含n+1个元素）。现假定E为单峰的，就说存在某个索引值为M，对于小于索引M的元素是顺序递增的，而对于大于索引M的元素是顺序递减的。这时E[M]为最大值元素。（注意，M可以是0或者n）现在的问题就是找到这个M。 a) 作为热身动作，说明当n＝2时，两次比较是必须的，并且是充分的。 因为在3个元素中找到其中最大值，通过两次比较是必须的，而且是充分的。 b) 写出通过比较E中的元素来查找M的算法。 算法策略为找到序列中第一个逆序，则该逆序的第一个元素即为M。 void getM(Element[] E){ for( int i=0; i。说明该算法共比较了多少次。 将n个元素排序是 的，并且在排序的时候在遇到有相等情况的时候会自动的停止排序或报告该信息。如果在排序的过程中没有出现相等的情况，则说明该序列中所有的元素都是互不相同的。（所有相邻的元素在最后一次排序时都要直接进行比较，否则算法不能确定序列已经被排序了。）所以总的时间是 的。 如果在使用排序算法的时候考虑到了相等的情况，则对已经排序过的序列判断其中是否有相同的键，只需要扫描一遍就可以了，所用的时间也是 的。所以总的时间还是 的。 b) 给出所需比较次数的下限。（试一试 ） 考虑序列中的所有元素都是互不相同的。假定排序后元素为 。算法只有在获取了相邻元素 和 的相对关系后，才具有用于排序的足够信息。 假定存在两个元素 和 ，算法并没有获取关于它们的相对位置的信息。这时，算法并没有足够的信息确定 ，因为这些元素同序列中其他元素的比较不能提供这样的信息。这时，该算法声明该序列中有两个相等的元素的结论是错误的。这时，如果该算法声明该序列中所有元素都是互不相同的，则只需要更改 ，使其等于 ，这时的更改对其他的比较结果是没有影响的，所以算法给出了一个错误的结论。 因此，为判断序列中没有相等的元素，算法也必须像排序那样收集到足够的信息才可以。这时看来虽然时间下限都是 的，但是三路（＝，<和>）比较相对与两路（<和>）对于解决该问题更加有效。但是如果序列中的所有元素都是互不相同的，则对于“＝”的比较并不会提供任何有用的信息。所以在最坏情况下，对n个元素进行排序还是需要 的，因此确定序列中是否有相同元素所需要的比较次数，在最坏情况下仍然是 的。 5.20 考虑判定长度为n的位串是否含有两个连续0的子串的问题。基本的操作方式是检测位串的每一个位置，看该位置是0还是1。对于 给出算法。 boolean getTwo0( Bit[] E) { count = 2; for (i=0; i
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
如下： 1、 为每一个元素中的“相等数”初始化为1； 2、 将最底层的n个元素两两比较，如果左右儿子的元素相等，则新建节点的“键值”为左儿子，“相等数”为左右儿子“相等数”之和；否则，新节点的“键值”可以左右儿子的任意一个，这里假设为较大的那一个，“相等数”为1；同时，记录“相等数”最大的那个节点的信息。 3、 顺序按层两两比较，处理方法同2； 4、 这样经过n-1次比较后，就选出了这n个元素中的最大值，同时也得到了“相等数”最大的那个节点的信息，设为M； 5、 如果M.相等数>＝2，则以该节点的元素值同序列中的所有元素进行相等比较，并记录相等计数，如果该计数大于n/2，则输出该元素；否则，直接输出-1。 5.24 设M为一个 的整数矩阵，其中每一行的元素是递增的（从左至右），每一列的元素是递增的（从上至下）。考虑这样的一个问题，判定整数x在M中的位置，或者确定x不在M中。以策论的观点给出解决该问题的比较次数的下限。该算法允许以三种方式比较x和M[i][j]，比较结果为 。 注意：解决该问题的高效算法为第四章的习题4.58。如果算法设计和策论观点足够的好，则该算法的比较次数同该算法的下限是相同的。 6.1 在需要扩大序列时，所使用的策略是两倍复制当前序列。现在要使用四倍来复制当前序列，评估这种策略的时间和空间耗费。 假定在有向序列中插入第（n+1）个元素的时候，触发了双倍复制序列操作。设当从旧序列中复制一个元素到新序列时的时间消耗为t（在这里设定t为某一固定值）。则在将旧序列复制到新序列的时候需要进行n次传输操作。而这次在前一次双倍复制操作已经进行了 次传输，再前次是 ，并以此类推。则总的时间消耗为 。如果使用四倍复制策略，则总的时间消耗为 ，即 。对于空间消耗，四倍复制策略会分配所需求空间总量的四倍，而两倍复制策略会分配所需求空间总量的两倍。 6.2 为保存栈的空间，在被分配的存储空间存在片断的时候会进行适当的收缩。这可以作为对双倍数组负责策略的补充。 假设在栈大小超出已分配空间大小的时候，所使用的分配策略为双倍复制。使用“已摊销成本”方式，评估以下收缩策略。每次操作是否消耗固定的“已摊销成本”的时间 a) 如果pop操作后栈元素数少于 时，收缩栈的大小为 。 在最坏情况下的时间复杂度为 的。假定栈大小为 ，当前栈中已经有n个元素（大小为 ）。这时如果连续执行两次push操作就会触发双倍复制动作，所需要的时间为 ，栈大小变为 。现在如果再连续进行两次pop操作，栈中的元素个数变为n，也就是 。这时就会触发收缩动作，该操作的时间消耗为 。综合这四次操作总的时间消耗为 。按照上述过程无限重复，则在最坏情况下的时间复杂度为 的。 b) 如果pop操作后栈元素数少于 时，收缩栈的大小为 。 各操作的时间耗费如下： 1. push操作，如果没有触发“双倍复制”操作，则时间消耗为2t； 2. push操作，如果触发了“双倍复制”操作，则时间消耗为： 3. pop操作，如果没有“收缩”，则时间消耗为：2t； 4. pop操作，如果触发了“收缩”操作，则时间消耗为： 。 c) 如果pop操作后栈元素数少于 时，收缩栈的大小为 。 d) 6.3 说明定义6.1的第三点是必须的。也就是说所画的树不具有二叉查找树的属性（参见定义6.3），但是满足定义6.1的第一点和第二点，并且从左至右扫描该树，在遇到升序的键值的时候清除这条垂直线。 如果不满足定义6.1的第三点，则可能会画出如下的树： 6.4 画出所有的RB1树和RB2树，与所有的ARB1树和ARB2树。 相关内容： 定义6.5 树和 树 已知结点只有红色和黑色两种形式，所有外部结点都为黑色结点的二叉树，则按照如下定义 树和 树： 1. 一个外部结点是一棵 树。 2. 对于 ，如果二叉树的根是红色的，并且它的左右子树都是 树，则该树是一棵 树。 3. 对于 ，如果二叉树的根是黑色的，并且它的左右子树或是一棵 树，或是一棵 树，则该树是一棵 树。 6.5 证明定理6.1。 相关内容： 定理6.1 对满足定义的 树和 树的黑色高度为h。 证明： 1. 当 时，对于 ，其仅为一个外部结点，黑色高度为0；由于 不存在，则黑色高度也是0；当 时，对于 和 ，在练习6.4中可以判断它们的黑色高度为1。 2. 假定对于 ， 和 的黑色高度为j，现证明在 时， 和 的黑色高度为k。 对 树，该树是由一个红色根结点和两棵 树组成，在根结点和这两棵子树之间的边为黑色边，即 的黑色高度为 。 对于 树，该树是由一个黑色根结点和两棵子树组成，这些子树或者是 或者是 。若这两棵子树都是 ，则 的黑色高度为 ；若这两棵子树中至少含有一棵 ，则 的黑色高度为 。 根据假设有 ，所以 ，即 和 的黑色高度为都为k。 综合1和2，则命题得证，即对满足定义的 树和 树的黑色高度为h。 6.6 证明定理6.2。 相关内容： 定理6.2 假定T为一棵 树。也就说T为一棵红-黑树，该树黑色高度为h。则： 1、T至少有 个内部黑色结点。 2、T至多有 个内部节点。 3、任何黑色结点的深度至多为该结点黑色深度的两倍。 假定A为一棵 树。也就说A为一棵类似红-黑树的二叉树，该树的黑色高度也是h。则： 1、A至少有 个内部黑色结点。 2、A至多有 个内部节点。 3、任何黑色结点的深度至多为该结点黑色深度的两倍。 证明： 1. 设 树和 树的黑色高度为h。则当 时，对于 树，该树由一个外部结点组成，显然对于上述的定理是成立的。而对于 树，该树是不存在的，也显然对于上述的定理是成立的。 2. 假定 ，对所有 的所有j上述定理都成立。现证明在 时，上述定理都成立。 对于 树，由于该树是由红色的根结点和两棵 子树组成。根据上述的假设，则该树的内部黑色结点至少为 ；该树的内部结点至多有 。 对于 树，由于该树是由黑色的根节点和两棵子树组成，这些子树或者是 树或者是 ，所以组成这棵 树的组成情况分如下三种： 1. 黑色根结点，两棵 子树； 2. 黑色根结点，一棵 子树和一棵 子树； 3. 黑色根结点，两棵 子树。 在上述三种情况中，第一种情况下所含的结点数最少，第三种情况下所含的结点数最多。所以该 树的内部黑色结点至少为 ；内部结点至多有 。 对于符合定义的 树和 树，是不允许存在红色结点到红色结点的边，所以从根（黑色结点）到任何黑色结点的路径上，所包含的红色结点数至多为路径上所有结点数目的一半，而每一个黑色结点（除去根结点外）带一条黑色的边，每一个红色结点带一条非黑色的边。所以“任何黑色结点的深度至多为该结点黑色深度的两倍”。 6.7 为什么“颜色漂移”策略不能处理含有三个节点的“冲突簇”？ 因为“颜色漂移”策略的初始条件为首先要有一个黑色结点的根，另外这个根还需要有两个红色的孩子结点，而这在只有3个结点的“冲突簇”中是没法满足的。 6.8 从空的红-黑树开始，在其中插入关键字10，20，30，40，50，60，70，80，90和100。 相关内容： 1、 按照向二叉查找树中插入结点的方法，找到插入位置； 2、 在插入结点后，更新的红-黑树； 在未插入新结点前，“簇”的形式有四种： 在插入新的结点后，会在后三种形式中产生“冲突簇”： 一种是4结点的： 修正方法：对于含有4个结点的“冲突簇”使用“颜色漂移”的方法，即将当前的黑结点和它的两个红结点儿子的颜色都反过来。 另一种是3结点的： 修正方法：对含有3个结点的“冲突簇”使用“旋转”的方法，即将上述的含3个结点的“冲突簇”都通过“旋转”变换为： 6.9 写出一个合适的序列，该序列顺序向一个空的红-黑树中插入15个结点，最终得到的新红-黑树的黑色高度为2。 6.10 为算法6.2写出下列颜色相关子程序。 a) 函数colorOf，如果输入参数为空树，则输出black；否则输出树根的颜色。 int colorOf( RBtree T ) { if (T == nil) return balck; else return T.color; } b) colorFlip，参见6.4.5节。 void colorFlip( RBtree T) { T.leftSubtree.color = black; T.rightSubtree.color = black; T.color = red; } 6.11写出算法6.2的repairRight和rebalRight子程序 InsReturn repairRight( RBtree oldTree, InsReturn ansRight) { InsReturn ans = new InsReturn(); if (ansRight.status == ok) { ans.newTree = oldTree; ans.status = ok; } else { oldTree.rightSubtree = ansRight.newTree; if (ansRight.status == rbr) { ans.newTree = oldTree; ans.status = ok; } else if (ansRight.status == brb) { if (oldTree.color == black) ans.status = ok; else ans.status = rrb; ans.newTree = oldTree; } else if (colorOf(oldTree.leftSubtree) == red) { colorFlip(oldTree); ans.newTree = oldTree; ans.status = brb; } else { ans.newTree = rebalRight(oldTree, ansRight.status); ans.status = ok; } } return ans; } RBtree rebalRight(RBtree oldTree, int rightStatus) { RBtree L,M,R,LR,RL; if (rightStatus == brr) { L = oldTree; M = oldTree.rightSubtree; R = M.rightSubtree; LR = M.leftSubtree; L.rightSubtree = LR; M.leftSubtree = L; } else { L = oldTree; R = oldTree.rightSubtree; M = R.leftSubtree; LR = M.leftSubtree; RL = M.rightSubtree; L.rightSubtree = LR; R.leftSubtree = RL; M.leftSubtree = L; M.rightSubtree = R; } L.color = red; R.color = red; M.color = black; return M; } 6.12 证明定理6.4。 相关内容： 定理6.4 如果rbtlns的参数oldRBtree为一棵 树或者为一棵 树，则newTree和status的返回组合为： 1. status = ok，newTree树为一棵 树或者为一棵 树； 2. status = rbr，newTree树为一棵 树； 3. status = brb，newTree树为一棵 树； 4. status = rrb，newTree.color＝red，newTree.leftSubtree是一棵 树，newTree.rightSubtree是一棵 树； 5. status = brr，newTree.color＝red，newTree.rightSubtree是一棵 树，newTree.leftSubtree是一棵 树； 证明： 由于函数rbtlns是相对于h递归调用的，所以可以使用归纳法证明上述定理。 1. 当h=0时， 6.13说明在一次插入操作后（图6.9），在通过旋转方式进行平衡修正时所做的结构变化。提示
浙公网安备 33021202002483