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

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

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

3、-1)次比较。：(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

4、+k)，其中E(i)>E(i+k)。而根据没有一对相邻元素需要交换位置的条件，又有E(i+k)>E(i+k-1)>>E(i+1)>E(i)，这是矛盾的。：(a)证明：根据(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(Element E, int n) int numPairs; int last; int j; last

5、= 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的每个过程都循环一遍。不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同

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

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

8、hile (remUnsort != null) int newE = first(remUnsort); sorted = insertl(newE,sorted); remUnsort = rest(remUnsort); return sorted;算法分析：假设unsorted有n个元素。当sorted已经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为的，平均情况和最坏情况的时间消耗为的。调用insertl时，变量k的变化范围为0n-1的。因此在整个过程中的时间复制度，最好为，平均和最坏为extendSmallRegion的后置条件为：在元素Elow,.,Ehigh

9、Vac-1中最左面一个“枢纽”的元素将被移动到EhighVac中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。对于已经排序的序列，进行快速排序将会进行次比较和次移动。Efirst被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。考虑含有k个元素的一个子区域。选择“枢纽”需要3（）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总共需要进行k次的比较。这相对于简单的选择Efirst作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择Efirst 、E(first+last)/2和Elast的时候，总是选

10、中了两个序列中最小的两个元素，这样每次都选中序列中第二小的元素做“枢纽”的话，总的比较次数是次。所以说对于逆序输入的序列进行快速排序，如果采用选择Efirst 、E(first+last)/2和Elast的中间元素作为“枢纽”的方法的时间复制度仍然是的。(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)）次。在第二次调用

11、后序列为：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次移动。（a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动，概率为。所以对k个元素进行排序的平均移动次数为。因此使用p

12、artitionL的快速排序的移动次数大约为。（b）在partition中，每个 “unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”枢纽元素的时候需要移动，概率为；在extendLargeRegion中，“unknown”元素在“小于”枢纽元素的时候需要移动，概率为。所以平均的移动次数为。因此使用partition的快速排序的移动次数大约为（c）使用partition的快速排序将使用次比较和次移动。归并排序的时间复制度大约是。IntList listM

13、erge(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(i

14、n2); 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); 方案1：设P（k，m）为归并排序k个元素的序列和m个元素的交换数，其中nkm。则：If A0

15、< 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个位置的输出序列以二叉树表示，分别需要的选择方案为。如果输入序列是已排序的，这合并两个子序列需要次比较就可以了。递归表示为：，如果n是2的整数次幂，则，如果使得，则。（a）修改算法Mergesort，增加一个工作序列的参数。在Mergesort之上添加mer

16、geSortWrap，用于初始工作序列：mergeSortWrap(Element E, int first, int last) Element W = new Element; mergeSort(E, E, W, first, last);修改后的Mergesort为：mergeSort(Element in, Element out, Element work, int first, int last) if (first = last) if (in != out) outfirst = infirst; else mid = (first + last) / 2; mergeSor

17、t(in, work, out, first, mid); mergeSort(in, work, out, mid + 1, last); merge(work, first, mid, last, out); 虽然该算法需要三个序列参数，但是实际使用中仅有两个E和W。（b）由于输入序列和输出序列为不同的区域，所以现在merge在每次比较的时候都需要一次移动。所以对于mergesort来说，移动次数将是。而对于快速排序，平均移动次数为对于深度为（D-1）的递归树共有个叶子结点，其中有个叶子可以有两个孩子，所以在深度为D的递归树中有个叶子。因此，即。<<<<<2:

18、02:02:02:02:02,0,11,2,01,0,22,1,00,1,20,2,1这不是大顶堆，因为5小于它的右孩子7。“COMPLEXITY”初始化为大顶堆后为“YTXPOEMICL”，比较次数为14次（2+1+2+2+1+2+2+2）。(a) 共需要9次；(b) 因为待排序序列已经是降序的，所以在初始建堆时，每次调用FixHeap仅做一次或两次比较就可以了，并且不会有元素的移动。因为堆结构所使用的二叉树为“左完全二叉树”，所以有如下已知条件：1、如果已知有n个结点，则该二叉树有n-1条边。现分条件说明初始建堆时的比较次数：1、如果n为偶数，则最后一个内部结点只有一个左儿子，该结点仅需要

19、一次比较；这时有两个孩子的结点个数为（根据已知条件1），这些结点需要两次比较。所以总的比较次数为次。2、如果n为奇数，则所有内部结点都有两个孩子，这些结点都需要两次比较，则总的比较次数为次。综合1和2，当n为正整数时，总的比较次数为n-1次。(c) 对算法（初建堆）来说是最好的情况，因为只需要n-1次比较，没有元素的移动。在推出for循环后，应该附加条件E1ßàE2（交换E1和E2）。这种改变仅仅是减少了在调用FixHeap时的过顶处理，并没有减少比较次数。（a）K = H100 = 1。将100从H1中移出；开始fixHeapFast，vacant = 1 h = 6。比

20、较 99, 98; 将 99 移到 H1中；vacant 是 H2；比较 97, 96; 将 97 移到 H2 中；vacant 是 H4；比较 93, 92; 将 93 移到 H4 中；vacant 是 H8；比较 K 与 H8 的父结点，该结点为 93。K 小，继续，h = 3.比较 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插

21、入到 H64.（b）4329；（c）fixHeap做了12次比较，除了叶子外每一层次比较了2次。证明：左边如果h为奇数，这时，所以；如果h为偶数，这时，但是h+1为奇数，所以为非整数，所以（说明：因为，且h为偶数，所以h的最小值为2，考虑函数。）综上所述，对于一切整数h，且，有假定希尔排序共分5个阶段，并且每一阶段的递增量为常数。再假定这5个递增量中的最大值为k，在最坏情况（倒序序列）下进行排序。在第一阶段将元素分成了k组，每一组大约为n/k个元素，这时对每一组进行直接插入排序，因为每一组元素的顺序也是倒序的，根据对最坏情况下直接插入排序的算法复杂度分析有，所以每一组的时间约为，k组总共的时间

22、约为，由于k为常数，所以。同样道理，在其他阶段所用的时间不会多于第一阶段的时间，也就是不会超过的量级，但是总的时间复制度仍然是如果m减半，基数radix取其平方数。因为。 画出当n为4时，算法FindMax（算法）的判定树。 我们以策论的观点分析了查找n个元素中最大元素和最小元素算法的下限。而如果以判定树的观点我们会得到什么样的下限呢 基于堆结构（节）写一个查找max（最大元素）和secondLargest（第二大元素）的算法。a) 说明下述过程将max（最大元素）放置在E1中。序列E的索引为。heapFindMax(E,n) int last; Load n elements into En

23、,E2*n-1. for (last=2*n-2; last>=2; last-=2) Elast/2 = max(Elast,Elast+1);for循环对元素 顺序赋值，并没有对任何数据进行修改。使用归纳法证明调用函数heapFindMax后，每个位置的元素都是包含它在内的子树的最大值。对于最底层的叶子元素n到2n-1推论成立。现假设对所有位置大于k的元素该推论都成立，现考虑节点k。在对节点k赋值的时候，last为2k，这时位置k为其孩子2k和2k+1的最大值，而对于2k和2k+1，根据推论都是其子树的最大值，所以k为其子树的最大值。所以该推论成立，由此经过for循环后，E1中为最大

24、值。b) 说明如何判断有那些元素输给了winner。对于每一个内部节点都是它孩子的一个拷贝，在为该节点赋值的时候，另一个孩子节点就是失败者。现假设所有键值都不相同，则从根节点开始到其某个叶节点有一条道路，这条道路上的所有节点值都为max，在这条路上除叶节点之外，所有内节点的另一个孩子都是相对于max的失败者。c) 在heapFindMax后，继续完成查找secondLargest的算法。max = E1;secondLargest = ;i = 1;while (i < n) if (E2*i = max) i = 2*i;if (Ei+1 > secondLargest)seco

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

26、 E1; second = E2;else max = E2; second = E1;for (i = 3; i<= n; i+) if (Ei > second) second = max; max = Ei; else second = Ei;a) 该算法在最坏情况下要比较多少次给出当n=6时的最坏情况。在最坏情况下的比较次数为次。最坏情况会在输入序列为逆序时发生。b) 给出在输入为n时，该算法的平均比较次数。在每次循环中比较次数为一次或两次，并且至少比较一次。只有在Ei为前i个元素中最大的两个的时候会比较两次，这时的概率为，而对于比较一次的概率为。另外，在进入循环之前还比较

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

28、ement = Efirst;Key pivot = ;int splitPoint = partition(E, pivot, first, 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查找中间元素时，最坏情况

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

30、切的递归方程式。设为当n个元素中k的位置为最坏情况式的平均比较次数，即为，所以：d) 分析你的算法的平均运行时间。给出渐进估计。根据上述的递归方程，可以猜想，其中c为某一个确定的常数。为证明该假设，根据上述的简化的递归方程有：为保证该不等式成立，并取得适当的常数c，因为，则可取。 假定使用如下算法查找n个元素中第k大的元素。Build a heap H out of the n keys;for (i=1; i<=k; i+)output(getMax(H);deleteMax(H);在k值取何值时，该算法的时间复杂度为线性的。在最坏情况下建堆需要次比较。如果在堆中含有m个元素，则使用F

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

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

33、中的所有元素进行相等比较，并记录相等计数，如果该计数大于n/2，则输出该元素；否则，直接输出-1。 设M为一个的整数矩阵，其中每一行的元素是递增的（从左至右），每一列的元素是递增的（从上至下）。考虑这样的一个问题，判定整数x在M中的位置，或者确定x不在M中。以策论的观点给出解决该问题的比较次数的下限。该算法允许以三种方式比较x和Mij，比较结果为。注意：解决该问题的高效算法为第四章的习题。如果算法设计和策论观点足够的好，则该算法的比较次数同该算法的下限是相同的。 在需要扩大序列时，所使用的策略是两倍复制当前序列。现在要使用四倍来复制当前序列，评估这种策略的时间和空间耗费。假定在有向序列中插入第

34、（n+1）个元素的时候，触发了双倍复制序列操作。设当从旧序列中复制一个元素到新序列时的时间消耗为t（在这里设定t为某一固定值）。则在将旧序列复制到新序列的时候需要进行n次传输操作。而这次在前一次双倍复制操作已经进行了次传输，再前次是，并以此类推。则总的时间消耗为。如果使用四倍复制策略，则总的时间消耗为，即。对于空间消耗，四倍复制策略会分配所需求空间总量的四倍，而两倍复制策略会分配所需求空间总量的两倍。 为保存栈的空间，在被分配的存储空间存在片断的时候会进行适当的收缩。这可以作为对双倍数组负责策略的补充。假设在栈大小超出已分配空间大小的时候，所使用的分配策略为双倍复制。使用“已摊销成本”方式，评

35、估以下收缩策略。每次操作是否消耗固定的“已摊销成本”的时间a) 如果pop操作后栈元素数少于时，收缩栈的大小为。在最坏情况下的时间复杂度为的。假定栈大小为，当前栈中已经有n个元素（大小为）。这时如果连续执行两次push操作就会触发双倍复制动作，所需要的时间为，栈大小变为。现在如果再连续进行两次pop操作，栈中的元素个数变为n，也就是。这时就会触发收缩动作，该操作的时间消耗为。综合这四次操作总的时间消耗为。按照上述过程无限重复，则在最坏情况下的时间复杂度为的。b) 如果pop操作后栈元素数少于时，收缩栈的大小为。各操作的时间耗费如下：1. push操作，如果没有触发“双倍复制”操作，则时间消耗为

36、2t；2. push操作，如果触发了“双倍复制”操作，则时间消耗为：3. pop操作，如果没有“收缩”，则时间消耗为：2t；4. pop操作，如果触发了“收缩”操作，则时间消耗为：。c) 如果pop操作后栈元素数少于时，收缩栈的大小为。d) 说明定义的第三点是必须的。也就是说所画的树不具有二叉查找树的属性（参见定义），但是满足定义的第一点和第二点，并且从左至右扫描该树，在遇到升序的键值的时候清除这条垂直线。如果不满足定义的第三点，则可能会画出如下的树： 画出所有的RB1树和RB2树，与所有的ARB1树和ARB2树。相关内容：定义 树和树已知结点只有红色和黑色两种形式，所有外部结点都为黑色结点的

37、二叉树，则按照如下定义树和树：1. 一个外部结点是一棵树。2. 对于，如果二叉树的根是红色的，并且它的左右子树都是树，则该树是一棵树。3. 对于，如果二叉树的根是黑色的，并且它的左右子树或是一棵树，或是一棵树，则该树是一棵树。 证明定理。相关内容： 定理 对满足定义的树和树的黑色高度为h。证明：1. 当时，对于，其仅为一个外部结点，黑色高度为0；由于不存在，则黑色高度也是0；当时，对于和，在练习中可以判断它们的黑色高度为1。2. 假定对于，和的黑色高度为j，现证明在时，和的黑色高度为k。对树，该树是由一个红色根结点和两棵树组成，在根结点和这两棵子树之间的边为黑色边，即的黑色高度为。 对于树，该

38、树是由一个黑色根结点和两棵子树组成，这些子树或者是或者是。若这两棵子树都是，则的黑色高度为；若这两棵子树中至少含有一棵，则的黑色高度为。根据假设有，所以，即和的黑色高度为都为k。综合1和2，则命题得证，即对满足定义的树和树的黑色高度为h。 证明定理。相关内容：定理假定T为一棵树。也就说T为一棵红-黑树，该树黑色高度为h。则：1、T至少有个内部黑色结点。2、T至多有个内部节点。3、任何黑色结点的深度至多为该结点黑色深度的两倍。假定A为一棵树。也就说A为一棵类似红-黑树的二叉树，该树的黑色高度也是h。则：1、A至少有个内部黑色结点。2、A至多有个内部节点。3、任何黑色结点的深度至多为该结点黑色深度

39、的两倍。证明：1. 设树和树的黑色高度为h。则当时，对于树，该树由一个外部结点组成，显然对于上述的定理是成立的。而对于树，该树是不存在的，也显然对于上述的定理是成立的。2. 假定，对所有的所有j上述定理都成立。现证明在时，上述定理都成立。对于树，由于该树是由红色的根结点和两棵子树组成。根据上述的假设，则该树的内部黑色结点至少为；该树的内部结点至多有。对于树，由于该树是由黑色的根节点和两棵子树组成，这些子树或者是树或者是，所以组成这棵树的组成情况分如下三种：1. 黑色根结点，两棵子树；2. 黑色根结点，一棵子树和一棵子树；3. 黑色根结点，两棵子树。在上述三种情况中，第一种情况下所含的结点数最少

40、，第三种情况下所含的结点数最多。所以该树的内部黑色结点至少为；内部结点至多有。对于符合定义的树和树，是不允许存在红色结点到红色结点的边，所以从根（黑色结点）到任何黑色结点的路径上，所包含的红色结点数至多为路径上所有结点数目的一半，而每一个黑色结点（除去根结点外）带一条黑色的边，每一个红色结点带一条非黑色的边。所以“任何黑色结点的深度至多为该结点黑色深度的两倍”。 为什么“颜色漂移”策略不能处理含有三个节点的“冲突簇”因为“颜色漂移”策略的初始条件为首先要有一个黑色结点的根，另外这个根还需要有两个红色的孩子结点，而这在只有3个结点的“冲突簇”中是没法满足的。 从空的红-黑树开始，在其中插入关键字

41、10，20，30，40，50，60，70，80，90和100。相关内容：1、 按照向二叉查找树中插入结点的方法，找到插入位置；2、 在插入结点后，更新的红-黑树；在未插入新结点前，“簇”的形式有四种：在插入新的结点后，会在后三种形式中产生“冲突簇”：一种是4结点的：修正方法：对于含有4个结点的“冲突簇”使用“颜色漂移”的方法，即将当前的黑结点和它的两个红结点儿子的颜色都反过来。另一种是3结点的：修正方法：对含有3个结点的“冲突簇”使用“旋转”的方法，即将上述的含3个结点的“冲突簇”都通过“旋转”变换为： 写出一个合适的序列，该序列顺序向一个空的红-黑树中插入15个结点，最终得到的新红-黑树的黑

42、色高度为2。 为算法写出下列颜色相关子程序。a) 函数colorOf，如果输入参数为空树，则输出black；否则输出树根的颜色。int colorOf( RBtree T ) if (T = nil) return balck; else return ;b) colorFlip，参见节。void colorFlip( RBtree T) = black; = black; = red;写出算法的repairRight和rebalRight子程序InsReturn repairRight( RBtree oldTree, InsReturn ansRight) InsReturn ans =

43、new InsReturn(); if = ok) = oldTree; = ok;else = ; if = rbr) = oldTree; = ok;else if = brb) if = black) = ok; else = rrb; = oldTree;else if (colorOf = red) colorFlip(oldTree); = oldTree; = brb;else = rebalRight(oldTree, ; = ok;return ans;RBtree rebalRight(RBtree oldTree, int rightStatus) RBtree L,M,

44、R,LR,RL; if (rightStatus = brr) L = oldTree; M = ; R = ; LR = ; = LR; = L;else L = oldTree; R = ; M = ; LR = ; RL = ; = LR; = RL; = L; = R; = red; = red; = black;return M; 证明定理。相关内容：定理 如果rbtlns的参数oldRBtree为一棵树或者为一棵树，则newTree和status的返回组合为：1. status = ok，newTree树为一棵树或者为一棵树；2. status = rbr，newTree树为一棵树

45、；3. status = brb，newTree树为一棵树；4. status = rrb，red，是一棵树，是一棵树；5. status = brr，red，是一棵树，是一棵树；证明：由于函数rbtlns是相对于h递归调用的，所以可以使用归纳法证明上述定理。1. 当h=0时，说明在一次插入操作后（图），在通过旋转方式进行平衡修正时所做的结构变化。提示，修订后子树的最终根元素参加了所有的“旋转”操作。 按照如下规则删除在练习中构造的红-黑树的结点。a) 从原始红-黑树中顺序独立地逻辑删除各结点。1. 删除结点“10”：2. 删除结点“20”和删除结点“30”是相同的，因为删除结点“20”时，是

46、将“30”复制到原“20”结点上，然后删除结点“30”：3. 删除结点“40”和删除结点“50”是相同的，因为删除结点“40”时，是将“50”复制到原“40”结点上，然后删除结点“50”：4. 删除结点“60”和删除结点“70”是相同的，因为删除结点“60”时，是将“70”复制到原“60”结点上，然后删除结点“70”：5. 删除结点“80”、“90”和“100”也大致相同：b) 连续删除剩下部分的根结点。c) 连续删除剩下部分关键字最小的结点 顺序删除在练习中构建的红-黑树，每次删除其中的最大结点。删除结点“15”：删除结点“14”：删除结点“13”：删除结点“12”：删除结点“11”：删除结

47、点“10”：删除结点“9”，“8”：删除结点“7”，“6”：删除结点“5”，“4”：删除结点“3”，“2”： 说明在删除结点后，通过旋转方式重新平衡红-黑树时结构的变化（参见图）。如果l是红色的，则先调用rightRotate(l,s)，再调用leftRotate(p,l)。p是红色的，或者r是红色的，或者s是红色的，则只调用leftRotate(p,s)。 现使用的矩阵A，当i和j在等效类中的时候Aij为1，否则为0。for (k=1; k<=n; k+) if (Ajk = 1) Aik = 1;for (k=1; k<=n; k+) if (Aik = 1)总的比较次数为：

48、a) void hUnion( int t, int u) if (heightt > heightu) parentu = t; else parentt = u; if (heightt = heightu) heightu+; find(1)：4次对parent的访问；find(4)：2次对parent的访问；find(6)：3次对parent的访问；find(2)：2次对parent的访问；find(1)：2次对parent的访问。 二项树（也称作树）的定义如下：是带有一个结点的树。对于的是将一棵树的根连接到另一棵树的根上，作为它的一个孩子。现证明，如果T是一棵树，则T有个结点，

49、高度为k，并且仅有一个深度为k的结点。我们将深度为k的结点叫做的句柄。证明：1. 当时，是只带有一个结点的树，这时显然有个结点，高度为0，并且仅有一个深度为0的结点。2. 当时，假定对所有的都满足上述条件，即有个结点，高度为j，并且仅有一个深度为j的结点。现证明对上述条件也成立。树是由两棵树的根连接而成，设这两棵树为和，并且是将连接到的树根上。1) 的结点数目为两棵子树结点数子和：；2) 的高度比的高度多1，所以为；3) 因为的最底层为的最底层，而的最底层为第k-1成，且仅有一个结点，所以的最底层为第k层，且也仅有一个结点。综合1和2可以证明，如果T是一棵树，则T有个结点，高度为k，并且仅有一

50、个深度为k的结点。 按照练习的定义和结论，证明的如下特性：假定T为一棵树，该树的句柄为v。树T可被分解为若干不相连的子树，这些子树中不包含v，这些子树的根结点为，分别说明如下：1. 是一棵树，其中；2. T由将v连接到，将连接到（）。1. 当k=1时，由两个结点组成，为一棵树，句柄v是的孩子。2. 当k>1是，假设对所有时满足上述特性，现在证明当j=k时也满足上述特性。树是由两棵树的根连接而成，设这两棵树为和，并且是将连接到的树根上。根据归纳假设的句柄为v，其不相连的树为，相关根结点为，如果将看作是，其根结点为，则满足上述描述，即的句柄为v，其中包含不相连的子树，根结点为。 按照练习的定

51、义和结论，证明树的如下特性：假定T为一棵树，该树的根为r，句柄为v。树T可被分解为若干不相连的子树，这些子树中不包含r，这些子树的根结点为，分别说明如下：1. 是一棵树，其中；2. T由将每一个连接到r上，（）；3. v是树的句柄。1. 当k=1时，由两个结点组成，为一棵树，其根结点为，树的句柄是v。2. 当k>1是，假设对所有时满足上述特性，现在证明当j=k时也满足上述特性。树是由两棵树的根连接而成，设这两棵树为和，并且是将连接到的树根上。根据归纳假设由根结点r，和不相连的树组成，这些树的根结点为。如果将看作是，其根结点为。而树的句柄v也就是树的句柄。所以满足上述描述，即的句柄为树的句

52、柄v，该树由根结点r和不相连的树组成，这些树的根结点为。 当n为2的整数次幂（）时获得最佳状态。首先插入n个元素会创建n棵只含有一个结点的树，这时并没有进行任何的比较。然后在调用getMax过程的时候，需要将这n棵树合并为一棵树，以确定其中的最大元素，这时需要进行n-1次比较。而该树共有个孩子。然后调用deleteMax删除最大元素（根元素），这时将该树分解为棵子树。再次调用getMax，这需要进行次比较，以获得第二大元素。即总的比较次数为次，这同在定理中得到的结论是一致的。 划这样一个无向连同图，该图的每个顶点都在某个无向圈中，但是无论如何导向这个无向图的边，在该图变成有向图后都不会是强连同的。 假定用图G描述二元关系R，则描述出R具有传递性的条件。对于图G中的任两个不同顶点v和w，如果在图G中存在一条从v到w的路径，则在图G中存在边vw。 画出对下图的深度优先搜索树，G为开始节点，存储条件：a邻接链表以字典序排列；b邻接链表以逆字典序排列。ab G为连通图，s为G中的一个顶点。TD是从s开始对G进行深度优先搜索形成的搜索树，TB是从s开始对G进行宽度优先搜索形