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

(a) 写出Maxsort算法。其中待排序序列为E，含有n个元素，脚标为范围为0,void Maxsort(Element[] E) { int maxID = 0;

for (int i=; i>1; i--) {

for (int j=0; jif (E[j] > E[maxID]) maxID = k; }

E[i] <--> E[maxID]; } }

,n1。

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

void bubbleSort(Element[] E, int n) { int numPairs; int last; int j;

last = n - 1; while(last>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的每个过程都循环一遍。

不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同时相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。

1,n,n-1,…,2 和 n,n-1,…,3,1,2 说明：将1放在n～2的逆序中任何位置都不改变最坏情况。

插入排序的最佳情况是序列已排序，这时候需要比较次数为n-1次，移动次数为0次。

(a) 最坏情况为插入位置在正数第2个位置，或者倒数第2个位置，比较次数[i/2]。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。

(b) 在最坏情况下插入位置在第1个位置上，移动次数为i次。

(c) 由于折半插入排序只是减少了比较的次数，并没有减少移动的次数，所以算法的时间复杂度仍然是O(n2)的。

(d) 采用链表数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-1)。但是这样也仅仅是减少了元素的移动时间，并没有减少元素的比较次数，所以算法的时间复制度仍然是O(n2)的。

首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均时间复制度会有所增加，因为在寻找插入位置的时候，会多比较那些相等的值。

含有n个元素的逆排序序列的逆序数为

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; }

n(n1)。 2算法分析：假设unsorted有n个元素。当sorted已经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为O(1)的，平均情况和最坏情况的时间消耗为O(k)的。调用insertl时，变量k的变化范围为0～n-1的。因此在整个过程中的时间复制度，最好为O(n)，平均和最坏为O(n2)

extendSmallRegion的后置条件为：在元素E[low],...,E[highVac-1]中最左面一个≥“枢纽”的元素将被移动到E[highVac]中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。

对于已经排序的序列，进行快速排序将会进行

n(n1)次比较和2(n1)次移动。E[first]2被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。

考虑含有k个元素的一个子区域。选择“枢纽”需要3（C32）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总共需要进行k次的比较。这相对于简单的选择E[first]作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择E[first] 、E[(first+last)/2]和E[last]的时候，总是选中了两个序列中最小的两个元素，

n2这样每次都选中序列中第二小的元素做“枢纽”的话，总的比较次数是次。所以说对于逆

4序输入的序列进行快速排序，如果采用选择E[first] 、E[(first+last)/2]和E[last]的中间元素作为“枢纽”的方法的时间复制度仍然是O(n2)的。

(a) 在第一次调用后序列为：1，9，8，7，6，5，4，3，2，10；移动1次。在第二次调用后序列不变，没有移动。对含有n个元素的逆序序列进行排序，调用partition的总的移

n动次数为，同时还需要加上在选择“枢纽”是用到的2(n1)次移动。

2(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)）次。总的移动次数为2in(n1)，另外还有在选择“枢纽”是用到的2(n1)次移动。

i1n1(c) partitionL的最大优点就是简单。在多数情况下，调用partitionL要比调用partition需要更多的移动次数。在a和b中，partitionL需要做90（10×9）次移动，而partition仅仅做了5（10/2）次移动。（另外完成快速排序还需要增加选择“枢纽”是用到的18次移动。

（a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动，

12(k1)概率为。所以对k个元素进行排序的平均移动次数为。因此使用partitionL的快

22速排序的移动次数大约为1.4nlgncn。

（b）在partition中，，每个 “unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”

1；在extendLargeRegion中，“unknown”元素在“小于”21(k1)枢纽元素的时候需要移动，概率为。所以平均的移动次数为。因此使用partition

22枢纽元素的时候需要移动，概率为

的快速排序的移动次数大约为0.7nlgncn

（c）使用partition的快速排序将使用1.4nlgn次比较和0.7nlgn次移动。归并排序的时间复制度大约是1.5nlgn。

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))); }

方案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)；

n所以P（k，m）＝P（k-1，m）＋P（k，m-1），P(k,m)。

k 方案2：在输出序列中共有m+k个位置，如果第一个序列中的k个元素在输出序列中的位置已经确定，则只需要将第二个序列中的m个元素顺序输出到输出序列中空缺的m个位置中就可以了。所以选择这k个位置的输出序列以二叉树表示，分别需要的选择方案为

mkmkmk,,...,。 12k

n如果输入序列是已排序的，这合并两个子序列需要2次比较就可以了。递归表示为： nnnW(n)W()W(),W(1)0，如果

222kn是2的整数次幂，则

nnnW(n)2kW(k)，如果使得klgn，则W(n)lgn。

22i12

（a）修改算法Mergesort，增加一个工作序列的参数。在Mergesort之上添加mergeSortWrap，用于初始工作序列：

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)

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来说，移动次数将是nlgn。而对于快速排序，平均移动次数为0.7nlgn

对于深度为（D-1）的递归树共有2D1个叶子结点，其中有(2D1B)个叶子可以有两个孩子，所以在深度为D的递归树中有2(2D1B)个叶子。因此，n2(2D1B)B2DB，即

B2Dn。

2:< 2:< 2:< 1,2,0 ≥ 2,1,0 ≥ 2,0,1 < 1,0,2 < 0,2,1 ≥ 2:≥ 2:≥ 0,1,2

2519537101241513 这不是大顶堆，因为5小于它的右孩子7。

“COMPLEXITY”初始化为大顶堆后为“YTXPOEMICL” ，比较次数为（2+1+2+2+1+2+2+2）。

(a) 共需要9次；

(b) 因为待排序序列已经是降序的，所以在初始建堆时，每次调用FixHeap仅做一次或两次比较就可以了，并且不会有元素的移动。因为堆结构所使用的二叉树为“左完全二叉树”，所以有如下已知条件：1、如果已知有n个结点，则该二叉树有n-1条边。现分条件说明初始建堆时的比较次数：

1、如果n为偶数，则最后一个内部结点只有一个左儿子，该结点仅需要一次比较；这时有两个孩子的结点个数为数为2*n2（根据已知条件1），这些结点需要两次比较。所以总的比较次214次

n21n1次。 2n1n1次。 22、如果n为奇数，则所有内部结点都有两个孩子，这些结点都需要两次比较，则总的比较次数为2*综合1和2，当n为正整数时，总的比较次数为n-1次。

(c) 对算法（初建堆）来说是最好的情况，因为只需要n-1次比较，没有元素的移动。

在推出for循环后，应该附加条件E[1]

E[2]（交换E[1]和E[2]）。这种改变仅仅是

减少了在调用FixHeap时的过顶处理，并没有减少比较次数。

（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次。 证明：

hh1左边＝lg()11lg(1)1lg(2(h2))

2221如果h为奇数，这时2(h2)h1，所以左边＝lg(h1)＝右边； 21如果h为偶数，这时2(h2)h2，但是h+1为奇数，所以lg(h1)为非整数，所以

2lg(h2)lg(h1)（说明：因为h1，且h为偶数，所以h的最小值为2，考虑函数

ylg(x1)lg(x)lg(x111） )lg(1)lg(1)1。

xx21综上所述，对于一切整数h，且h1，有lg(h1)1lg(h1)

2

假定希尔排序共分5个阶段，并且每一阶段的递增量为常数。再假定这5个递增量中的最大值为k，在最坏情况（倒序序列）下进行排序。在第一阶段将元素分成了k组，每一组大约为n/k个元素，这时对每一组进行直接插入排序，因为每一组元素的顺序也是倒序的，

n(n1)n2O(n2)，所以每一根据对最坏情况下直接插入排序的算法复杂度分析有W(n)22n2n21n组的时间约为，k组总共的时间约为，由于k为常数，所以O(n2)。同样道理，

2k2k2k2在其他阶段所用的时间不会多于第一阶段的时间，也就是不会超过O(n2)的量级，但是总的时间复制度仍然是O(n2)

wm2wm2如果m减半，基数radix取其平方数。因为radix2(2)。

画出当n为4时，算法FindMax（算法）的判定树。 ≥E[0]≥≥E[0]E[0]我们以策论的观点分析了查找n个元素中最大元素和最小元素算法的下限。而如果以判定树的观点我们会得到什么样的下限呢

基于堆结构（节）写一个查找max（最大元素）和secondLargest（第二大元素）的算法。 a) 说明下述过程将max（最大元素）放置在E[1]中。序列E的索引为1,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]);

,2n1。

for循环对元素E[n1]~E[1] 顺序赋值，并没有对任何数据进行修改。使用归纳法证明调用函数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;

给出通过竞争的策略查找第二大元素的平均比较次数。 a) 当n为2的整数次幂。 首先必须通过n-1次比较将最大元素排除，下面就是考虑相对于最大元素失败的元素最为候选的第二大元素的平均比较次数

b) 当n不是2的整数次幂。提示：参考练习。

以下算法通过持续的扫描序列，并将最大的两个元素保存下来的方法，查找含有n个元素的序列E的最大元素和第二大元素。（这里假设n2）

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时的最坏情况。 在最坏情况下的比较次数为12(n2)2n3次。最坏情况会在输入序列为逆序时发生。

b) 给出在输入为n时，该算法的平均比较次数。 在每次循环中比较次数为一次或两次，并且至少比较一次。只有在E[i]为前i个元素中最大的两个的时候会比较两次，这时的概率为

2(i2)，而对于比较一次的概率为。另外，ii在进入循环之前还比较了一次。所以平均比较次数为：

nnn2i21n11A(n)1(2)14121n22iii3i3ii3i3ii3i

n12(lnn1)n32lnnn 经过修改的快速排序可以查找n个元素中第k大的元素，并且在大多数情况下这时所需要的时间要比完全排序n个元素的时间少。 a) 为完成上述思想，实现修改后的快速算法findKth。 该算法的核心思想是在递归的使用Quicksort时会将序列分成两段，而对于findKth则仅仅需要对其中的某一段进行查找就可以了。

/** Precondition: firstklast */

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 = ;

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查找中间元素时，最坏情况为O(n2)。 在进行快速排序的时候，最坏情况为每次调用partition的时候只是分出一个元素来。

n如果输入序列为已排序的，则使用findKth查找中间元素的调用为findKth(E,1,n,)，这时

2会递归的使用first1,2,n,和lastn来调用findKth。其内部也会递归的使用该值调用2partition。根据对快速排序的分析，对这至少有

n个元素进行快速排序，在最坏情况下的比2较次数为O(n2)的。所以，findKth在最坏情况下的比较次数也是O(n2)的。

c) 为计算该方法的平均运行时间，列出其计算的递归方程。 设有n个元素，要查找的元素序号为k，则该算法平均运行时间的递归方程为：

n11k1T(n,k)n1T(n1i,k1i)T(i1,k) n1,0kn

ni0ik1T(1,0)=0

该算法的运行时间同比较次数近似相同。为避免含有两个参数的递归方程，我们可以通过一个上限表达式来替代确切的递归方程式。设T(n)为当n个元素中k的位置为最坏情况式的平均比较次数，即为T(n)maxT(n,k)，所以：

n11k1T(n)n1T(n1i)T(i1)

ni0ik1d) 分析你的算法的平均运行时间。给出渐进估计。 根据上述的递归方程，可以猜想T(n,k)cn，其中c为某一个确定的常数。为证明该假设，根据上述的简化的递归方程有：

n11k1111n1c(n1i)c(i1)n1k(n1nk)c(n1k)(kn2)cni0n22ik11c(n22kn2k23n2)2n1k31k1n(1c)k(cc())c(())12n22nnn1kcn为保证该不等式成立，并取得适当的常数c，因为k(cc())，则可取c4。

n4

假定使用如下算法查找n个元素中第k大的元素。

Build a heap H out of the n keys;

for (i=1; i<=k; i++) output(getMax(H)); deleteMax(H);

在k值取何值时，该算法的时间复杂度为线性的。

在最坏情况下建堆需要2n次比较。如果在堆中含有m个元素，则使用FixHeap的DeleteMax大约需要2lgm次比较。因此，for循环大约需要进行2(lgni)次比较。则总的

i1k比较次数的下界为2klgn，取k值为

n，则总的时间还是O(n)的。 lgn 给出查找n个元素中第k大元素的算法（1kn）。写出所有影响运行时间的执行细节，并给出该算法的时间复杂度描述，关于n和k的函数。

假设n为偶数，其中间元素为第中假定n为奇数）进行必要的修改。 无论n是奇数还是偶数都至少需要n1次“必要的”比较。策略论的策略是利用表中的

nn定义，其中S状态最多为1，L状态最多为。根据表中的定义，每一次比较最多产生一

22n个L状态，也最多产生一个S状态，而策略论的任何算法都可以至少剔除1次“非必要的”

2n比较。这时修改后的定理为：在n为偶数时，其中间元素为第小的元素。任何查找该中间

23n元素的算法，在最坏情况下至少需要2次比较。

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

1、CEX

E(3)E(4)lg(n1)0,,n1L00H0n1M01,2

n1LHn1R0nM222iLq1KE[i]LqLq1,HqHq1iHq1KE[i]LqLq1,HqHq1Lq1iMq1KE[i]Lqi1,HqHq1Mq1iHq1KE[i]Hqi1,LqLq1Rq1Hq1Lq12Rq112Rq112Rq112Hqi1Mq111Lq12Lq1LqLq1Rq1HqLq2Rq0LqHqRq1KE[Lq]Rq0R01n11Rq1(n1)2qqlg(n1)qlg(n1)0,,nO(n)nFkk2k1FkFk1Fk2k2Fk1lgn2n4O(logn)(1)(nlogn)(nlogn)O(n)(nlogn)(nlogn)x1x2xnxixi1xixi1xixi1xixi1(nlogn)(nlogn)(nlogn)n2,3,4,5nextmaxn1n1n1n1n111false22222n1n1n1(i1)(i1)(i1)1knk3nkw(i)1w(i)w(j)222E[i]E[j]w(i)w(i)w(j),w(j)0w(i)w(j)w(i)w(j)0E[i]E[j]E[i]E[j]w(i)w(i)w(j),w(j)0w(i)w(j)0nkw(j)w(i)w(j),w(i)0n(n2)等数>＝2，则以该节点的元素值同序列中的所有元素进2行相等比较，并记录相等计数，如果该计数大于n/2，则输出该元素；否则，直接输出-1。

设M为一个nn的整数矩阵，其中每一行的元素是递增的（从左至右），每一列的元素是递增的（从上至下）。考虑这样的一个问题，判定整数x在M中的位置，或者确定x不在M中。以策论的观点给出解决该问题的比较次数的下限。该算法允许以三种方式比较x和M[i][j]，比较结果为xM[i][j],x＝M[i][j]或xM[i][j]。

注意：解决该问题的高效算法为第四章的习题。如果算法设计和策论观点足够的好，则该算法的比较次数同该算法的下限是相同的。

在需要扩大序列时，所使用的策略是两倍复制当前序列。现在要使用四倍来复制当前序列，评估这种策略的时间和空间耗费。 假定在有向序列中插入第（n+1）个元素的时候，触发了双倍复制序列操作。设当从旧序列中复制一个元素到新序列时的时间消耗为t（在这里设定t为某一固定值）。则在将旧序列复制到新序列的时候需要进行n次传输操作。而这次在前一次双倍复制操作已经进行了

n次21n传输，再前次是，并以此类推。则总的时间消耗为Tit2tn。如果使用四倍复制策略，

4i02nn则总的时间消耗为nt,t,t,416，即Ti014tnt。对于空间消耗，四倍复制策略会分配4i3所需求空间总量的四倍，而两倍复制策略会分配所需求空间总量的两倍。

为保存栈的空间，在被分配的存储空间存在片断的时候会进行适当的收缩。这可以作为对双倍数组负责策略的补充。 假设在栈大小超出已分配空间大小的时候，所使用的分配策略为双倍复制。使用“已摊销成本”方式，评估以下收缩策略。每次操作是否消耗固定的“已摊销成本”的时间 a) 如果pop操作后栈元素数少于NN时，收缩栈的大小为。 22在最坏情况下的时间复杂度为(n)的。假定栈大小为N0，当前栈中已经有n个元素（大小为nN01）。这时如果连续执行两次push操作就会触发双倍复制动作，所需要的时间为

2tN0t，栈大小变为2N0。现在如果再连续进行两次pop操作，栈中的元素个数变为n，也

就是n2N0。这时就会触发收缩动作，该操作的时间消耗为2t(N01)t。综合这四次操作2总的时间消耗为2tN0t2t(N01)t3t2N0t2nt。按照上述过程无限重复，则在最坏情况下的时间复杂度为(n)的。

b) 如果pop操作后栈元素数少于各操作的时间耗费如下：

1. push操作，如果没有触发“双倍复制”操作，则时间消耗为2t； 2. push操作，如果触发了“双倍复制”操作，则时间消耗为：nt2t 3. pop操作，如果没有“收缩”，则时间消耗为：2t；

4. pop操作，如果触发了“收缩”操作，则时间消耗为：nt2t。

NN时，收缩栈的大小为。 44c) 如果pop操作后栈元素数少于 d)

NN时，收缩栈的大小为。 42 说明定义的第三点是必须的。也就是说所画的树不具有二叉查找树的属性（参见定义），但是满足定义的第一点和第二点，并且从左至右扫描该树，在遇到升序的键值的时候清除这条垂直线。 如果不满足定义的第三点，则可能会画出如下的树：

画出所有的RB1树和RB2树，与所有的ARB1树和ARB2树。 相关内容：

定义 RBh树和ARBh树

已知结点只有红色和黑色两种形式，所有外部结点都为黑色结点的二叉树，则按照如下定义RBh树和ARBh树： 1. 一个外部结点是一棵RBh树。

2. 对于h1，如果二叉树的根是红色的，并且它的左右子树都是RBh1树，则该树是一棵ARBh树。

3. 对于h1，如果二叉树的根是黑色的，并且它的左右子树或是一棵RBh1树，或是一棵ARBh树，则该树是一棵RBh树。

RB0ARB1RB1ARB2RB2ARB11相同共16种 ARB11相同共16种 ARB11相同共16种 ARB11相同共16种

证明定理。 相关内容：

定理 对满足定义的RBh树和ARBh树的黑色高度为h。

证明：

1. 当h0时，对于RB0，其仅为一个外部结点，黑色高度为0；由于ARB0不存在，则黑色高度也是0；当h1时，对于RB1和ARB1，在练习中可以判断它们的黑色高度为1。

2. 假定对于0jk，RBj和ARBj的黑色高度为j，现证明在hk时，RBk和ARBk的黑色高度为k。

对ARBk树，该树是由一个红色根结点和两棵RBk1树组成，在根结点和这两棵子树之间的边为黑色边，即ARBk的黑色高度为H(ARBk)H(RBk1)1。

对于RBk树，该树是由一个黑色根结点和两棵子树组成，这些子树或者是RBk1或者是

ARBk。若这两棵子树都是RBk1，则RBk的黑色高度为H(RBk)H(RBk1)1；若这两棵子树

中至少含有一棵ARBk，则RBk的黑色高度为

H(RBk)maxH(RBk1)1,H(ARBk)maxH(RBk1)1,H(RBk1)1H(RBk1)1。 根据假设有H(RBk1)k1，所以H(RBk1)1k11k，即ARBk和RBk的黑色高度为都为k。

综合1和2，则命题得证，即对满足定义的RBh树和ARBh树的黑色高度为h。 证明定理。 相关内容：

定理

假定T为一棵RBh树。也就说T为一棵红-黑树，该树黑色高度为h。则： 1、T至少有2h1个内部黑色结点。 2、T至多有4h1个内部节点。

3、任何黑色结点的深度至多为该结点黑色深度的两倍。

假定A为一棵ARBh树。也就说A为一棵类似红-黑树的二叉树，该树的黑色高度也是h。则：

1、A至少有2h2个内部黑色结点。

4h2、A至多有1个内部节点。 23、任何黑色结点的深度至多为该结点黑色深度的两倍。 证明：

1. 设RBh树和ARBh树的黑色高度为h。则当h0时，对于RB0树，该树由一个外部结点组成，显然对于上述的定理是成立的。而对于ARB0树，该树是不存在的，也显然对于上述的定理是成立的。

2. 假定h0，对所有0jh的所有j上述定理都成立。现证明在jh时，上述定理都成立。

对于ARBh树，由于该树是由红色的根结点和两棵RBh1子树组成。根据上述的假设，则该树的内部黑色结点至少为2(2h11)2h2；该树的内部结点至多有

2(4h14h1)11。

2对于RBh树，由于该树是由黑色的根节点和两棵子树组成，这些子树或者是RBh1树或者是ARBh，所以组成这棵RBh树的组成情况分如下三种：

1. 黑色根结点，两棵RBh1子树；

2. 黑色根结点，一棵RBh1子树和一棵ARBh子树； 3. 黑色根结点，两棵ARBh子树。

在上述三种情况中，第一种情况下所含的结点数最少，第三种情况下所含的结点数最多。所以该RBh树的内部黑色结点至少为2(2h11)12h1；内部结点至多有

4h2(1)14h1。

2对于符合定义的ARBh树和RBh树，是不允许存在红色结点到红色结点的边，所以从根（黑色结点）到任何黑色结点的路径上，所包含的红色结点数至多为路径上所有结点数目的一半，而每一个黑色结点（除去根结点外）带一条黑色的边，每一个红色结点带一条非黑色的边。所以“任何黑色结点的深度至多为该结点黑色深度的两倍”。

为什么“颜色漂移”策略不能处理含有三个节点的“冲突簇” 因为“颜色漂移”策略的初始条件为首先要有一个黑色结点的根，另外这个根还需要有两个红色的孩子结点，而这在只有3个结点的“冲突簇”中是没法满足的。

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

写出一个合适的序列，该序列顺序向一个空的红-黑树中插入15个结点，最终得到的新红-黑树的黑色高度为2。 481212356791011131415输入顺序为 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15

为算法写出下列颜色相关子程序。 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 = 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,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为一棵RBh树或者为一棵ARBh1树，则newTree和status的返回组合为：

1. status = ok，newTree树为一棵RBh树或者为一棵ARBh1树； 2. status = rbr，newTree树为一棵RBh树； 3. status = brb，newTree树为一棵ARBh1树；

4. status = rrb，＝red，是一棵ARBh1树，是一棵RBh树； 5. status = brr，＝red，是一棵ARBh1树，是一棵RBh树； 证明：

由于函数rbtlns是相对于h递归调用的，所以可以使用归纳法证明上述定理。 1. 当h=0时，RB0

说明在一次插入操作后（图），在通过旋转方式进行平衡修正时所做的结构变化。提示，修订后子树的最终根元素参加了所有的“旋转”操作。

按照如下规则删除在练习中构造的红-黑树的结点。 402010305060708090100 a) 从原始红-黑树中顺序独立地逻辑删除各结点。 1. 删除结点“10”：

6040203050708090100

2. 删除结点“20”和删除结点“30”是相同的，因为删除结点“20”时，是将“30”复制

到原“20”结点上，然后删除结点“30”：

60401030507080901006040102050708090100

3. 删除结点“40”和删除结点“50”是相同的，因为删除结点“40”时，是将“50”复制

到原“40”结点上，然后删除结点“50”：

50201030607080901004020103060708090100 4. 删除结点“60”和删除结点“70”是相同的，因为删除结点“60”时，是将“70”复制

到原“60”结点上，然后删除结点“70”：

40201030507080901004020103050608090100

5. 删除结点“80”、“90”和“100”也大致相同：

402010305060709010040201030506070801004020103050607080100

b) 连续删除剩下部分的根结点。 50201030607080901006020103070809010070201030809010020103080901002010309010020103010030101001010010 c) 连续删除剩下部分关键字最小的结点 604020305070809010060403050708090100604050708090100605070809010080607090100807090100908010090100100

顺序删除在练习中构建的红-黑树，每次删除其中的最大结点。 481212356791011131415

删除结点“15”：

4812123567910111314 删除结点“14”：

48121235679101113

删除结点“13”：

481112356791012

删除结点“12”：

4810123567911

删除结点“11”：

48123567910

删除结点“10”：

481235679

删除结点“9”，“8”：

474612356812357

删除结点“7”，“6”：

44123561235

删除结点“5”，“4”：

3212413

删除结点“3”，“2”：

121

说明在删除结点后，通过旋转方式重新平衡红-黑树时结构的变化（参见图）。 pglsr

如果l是红色的，则先调用rightRotate(l,s)，再调用leftRotate(p,l)。 p是红色的，或者r是红色的，或者s是红色的，则只调用leftRotate(p,s)。 现使用nn的矩阵A，当i和j在等效类中的时候A[i][j]为1，否则为0。

for (k=1; k<=n; k++) { if (A[j][k] == 1) A[i][k] = 1; }

for (k=1; k<=n; k++) { if (A[i][k] == 1) }

总的比较次数为：

n2(n1)(npn)n(n1)n(n3) 2p2n a)

void hUnion( int t, int u) { if (height[t] > height[u]) parent[u] = t; else {

parent[t] = u;

if (height[t] == height[u]) height[u]++; } }

942137689find(1)find(4)1243768find(6)find(2)find(1)12436798

find(1)：4次对parent的访问； find(4)：2次对parent的访问； find(6)：3次对parent的访问； find(2)：2次对parent的访问； find(1)：2次对parent的访问。

二项树（也称作Sk树）的定义如下：S0是带有一个结点的树。对于k0的Sk是将一棵

Sk1树的根连接到另一棵Sk1树的根上，作为它的一个孩子。

现证明，如果T是一棵Sk树，则T有2k个结点，高度为k，并且仅有一个深度为k的结点。我们将深度为k的结点叫做Sk的句柄。

证明：

1. 当k0时，S0是只带有一个结点的树，这时显然S0有201个结点，高度为0，并且仅有一个深度为0的结点。

2. 当k0时，假定对所有0jk的Sj都满足上述条件，即有2j个结点，高度为j，并且仅有一个深度为j的结点。现证明对Sk上述条件也成立。

Sk树是由两棵Sk1树的根连接而成，设这两棵树为Sk1和Sk'1，并且是将Sk'1连接到Sk1的

树根上。

1) Sk的结点数目为两棵子树结点数子和：22k12k； 2) Sk的高度比Sk1的高度多1，所以为(k1)1k；

3) 因为Sk的最底层为Sk'1的最底层，而Sk'1的最底层为第k-1成，且仅有一个结点，

所以Sk的最底层为第k层，且也仅有一个结点。

综合1和2可以证明，如果T是一棵Sk树，则T有2k个结点，高度为k，并且仅有一个深度为k的结点。

按照练习的定义和结论，证明Sk的如下特性：假定T为一棵Sk树，该树的句柄为v。树T可被分解为若干不相连的子树T0,T1,,Tk1，这些子树中不包含v，这些子树的根结点为

r0,r1,,rk1，分别说明如下：

1. Ti是一棵Si树，其中0ik1；

2. T由将v连接到r0，将ri连接到ri1（0ik1）。

1. 当k=1时，S1由两个结点组成，r0为一棵S0树，句柄v是r0的孩子。

2. 当k>1是，假设对所有1jk时Sj满足上述特性，现在证明当j=k时Sk也满足上述特性。

Sk树是由两棵Sk1树的根连接而成，设这两棵树为Sk1和Sk'1，并且是将Sk'1连接到Sk1的

树根上。根据归纳假设Sk'1的句柄为v，其不相连的树为T0,T1,,Tk2，相关根结点为

r0,r1,,rk2，如果将Sk1看作是Tk1，其根结点为rk1，则Sk满足上述描述，即Sk的句柄为

,Tk1，根结点为r0,r1,,rk1。

v，其中包含不相连的子树T0,T1, 按照练习的定义和结论，证明Sk树的如下特性：假定T为一棵Sk树，该树的根为r，句柄为v。树T可被分解为若干不相连的子树T0',T1',的根结点为r0',r1',,Tk'1，这些子树中不包含r，这些子树

,rk'1，分别说明如下：

1. Ti'是一棵Si树，其中0ik1；

2. T由将每一个ri'连接到r上，（0ik1）； 3. v是树Tk'1的句柄。

1. 当k=1时，S1由两个结点组成，T0'为一棵S0树，其根结点为r0'，T0'树的句柄是v。 2. 当k>1是，假设对所有1jk时Sj满足上述特性，现在证明当j=k时Sk也满足上述特性。

Sk树是由两棵Sk1树的根连接而成，设这两棵树为Sk1和Sk'1，并且是将Sk'1连接到Sk1的

树根上。根据归纳假设Sk1由根结点r，和不相连的树T0',T1',为r0',r1',,Tk'2组成，这些树的根结点

,rk'2。如果将Sk'1看作是Tk'1，其根结点为rk'1。而Sk'1树的句柄v也就是Sk树的

句柄。所以Sk满足上述描述，即Sk的句柄为Tk'1树的句柄v，该树由根结点r和不相连的树

T,T,'0'1,Tk'1组成，这些树的根结点为r0',r1',,rk'1。

当n为2的整数次幂（n2k）时获得最佳状态。首先插入n个元素会创建n棵只含有一个结点的树，这时并没有进行任何的比较。然后在调用getMax过程的时候，需要将这n棵树合并为一棵树，以确定其中的最大元素，这时需要进行n-1次比较。而该树共有log(n)个孩子。然后调用deleteMax删除最大元素（根元素），这时将该树分解为log(n)棵子树。再次

调用getMax，这需要进行log(n)1次比较，以获得第二大元素。即总的比较次数为

nlog(n)2次，这同在定理中得到的结论是一致的。

划这样一个无向连同图，该图的每个顶点都在某个无向圈中，但是无论如何导向这个无向图的边，在该图变成有向图后都不会是强连同的。

假定用图G描述二元关系R，则描述出R具有传递性的条件。 对于图G中的任两个不同顶点v和w，如果在图G中存在一条从v到w的路径，则在图G中存在边vw。

画出对下图的深度优先搜索树，G为开始节点，存储条件： a．邻接链表以字典序排列； b．邻接链表以逆字典序排列。 ABDGFCE 3/10ABD2/114/712/13G1/148/9FC5/6Ea．

7/12AB10/11DG1/146/13

F8/9C3/4E2/5b．

G为连通图，s为G中的一个顶点。TD是从s开始对G进行深度优先搜索形成的搜索树，TB是从s开始对G进行宽度优先搜索形成的搜索树。是否总有height(TD)height(TB)是否对有向图和无向图都是如此 总是有height(TD)height(TB)的。

假定v是对G宽度优先搜索形成搜索树的树根。对于该树中的任何顶点x，在从v到达x的路径中，由该树中的边形成的路径是最短的。（假定从v到达x的距离为其中经过的边数。）

证明方法为第二数学归纳法。假定v到x的距离是k，则当k＝0时，命题显然成立。先假设当k>0时，即点x到根v的距离是k，命题成立。则x不可能位于按宽度优先搜索形成的搜索树的k-1层以内。假定u是v到x的路径中距离x最近的一个顶点，则v到u的距离是k10，则u位于树的k-1层。根据前提假设，从v到u为最短路径，有因为x和u相邻，则v到x的最短路径为k，且在树的k层。

既然宽度优先搜索形成的搜索树是所有节点到达根节点距离最短的路径形成的，所以该树具有最小的深度。

给定图G以邻接链表形式表示，给出具有线性时间的算法，该算法计算出该图的转置图GT。 算法的基本思想是：

1、初始化一个新的邻接链表； InitNewAdjList(G’); 2、顺序扫描邻接链表 for (int i=0; i对于任何在list[i]中的节点x，将节点i加入到list[x]中； }

3、输出新的邻接链表。

在定义中的第二种情况种（黑色边），当边vw被检测到时w应该是什么颜色 灰色。

在对顶点进行搜索时，共有三种颜色分配给顶点。 白色顶点：未被访问的顶点；

灰色顶点：已经被访问过，但是以该顶点为根的搜索树还没有搜索完； 黑色顶点：已经被访问过，并且以该顶点为根的搜索树已经搜索完。 按照算法对下图按照深度优先搜索来归类各边。 a．顶点按字典序排列，每个链表内按字典序排列； b．顶点按逆字典序排列，每个链表内按字典序排列； c．顶点按字典序排列，每个链表内按逆字典序排列； d．顶点按逆字典序排列，每个链表内按逆字典序排列。 ABHDEFGCIJK 深度优先搜索树的根节点为黑色节点，黑色边为树中的边，虚线边为非树中的边，标志为b的边为反向边，c为交叉边，d为正向边。

定义： i. ii. iii. iv.

在搜索到vw时，w未被访问，则vw为树中的边，并且v是w的父节点； 如果w是v的祖先，则vw为反向边（其中包括vv）；

如果w是v的子孙，在访问vw时，w已经被访问，则vw称作正向边； 如果w和v没有任何关系（祖先/子孙），则vw为交叉边。

A1/22bA10/192/21BH9/2011/18bBH9/223/8DbcE10/1912/17DbcEc20/214/5FcG6/712/17IbC11/18FbJ13/1613/14cG15/162/7IbC4/5Jb3/6K14/15K1/8

假定v和w是相同有向树中不同的两个节点，但是这两个节点没有任何关系。显示距离v和w最近的祖先节点c。 算法思想：（根据提示，对于树中的每一个节点，都存在唯一的一条从根到该节点的路径。） 1、依次将节点w及其顺序父节点放入栈S1中（根节点位于栈顶）； 2、依次将节点v及其顺序父节点放入栈S2中（根节点位于栈顶）；

3、依次比较两个栈的栈顶元素，在第一次出现不同值时，上一次相同的值即为距离w和v最近的祖先节点。

写出确定一个图是否有回路的算法。 算法思想：

1、按照深度优先搜索该图，并在搜索过程中对所有的边归类； 2、如果在归类的边中出现反向边时，返回True（即该图有回路）； 3、否则，返回false（即该图无回路）。 拓扑编号算法：

1、按照深度优先搜索算法，计算每个顶点的完成时间f[v]； 2、在每个顶点完成访问后，将它插入链表的前端； 3、返回由顶点组成的链表。

按照书中算法，找出下图的强连同子图。 ABHDEFGCIJK 查找有向图中的极大连通子图的算法思想：

1、按照深度优先算法对图G进行访问，计算出图中每个顶点的完成时刻f[u]； 2、计算出该图对应的转置图GT；

3、按照深度优先算法对图GT进行访问，但在访问的过程中按照f[u]递减的顺序考虑各节点。

4、输出在第3步中产生的深度优先森林中的每棵树的节点，作为各自独立的强连通支。 证明对于无向连通图G的每条边，或者位于深度优先搜索树中或者是一条反向边。 证明：

对于图G中的任意边vw，假定顶点在深度优先搜索过程中先访问到v，再访问w。 1、访问边vw，在访问w之前；

2、访问vw，在访问w之后；

指出下图中的关节点有那些： ABCDIFGEHJ 按深度优先搜索图，形成深度优先生成树，由此判定关节点： 1、若生成树的根有两颗或两颗以上的子树，则此根顶点为关节点；

2、若生成树中的非叶子顶点v，其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边，则v是关节点。

首先A是关节点，因为A有两颗子树；另外还可以排除叶子结点；现分别考察非叶子节点：

B：不是，因为它仅有的一棵子树，有回边DA； D：是，因为它有子树F，没有回边； C：不是，它仅有一棵子树，且有回边IA； I：是，因为它仅有一棵子树，且无回边； E：不是，因为它仅有一棵子树，且有回边HI； H：不是，因为它仅有一棵子树，且有回边JE。 所以上图的关节点为：A，D和I。

找到并证明深度优先搜索树的根顶点是关节点的充分必要条件，并给予证明。 深度优先搜索树的根节点是关节点当且仅当根的儿子多于一个。 1、a是根，且a是关节点

a的儿子多于一个。

如果a只有一个儿子f，则除a以外的任何顶点必在以f为根的子树上。根据树的性质，以f为根的子树上的任何两点之间，都存在一条经过f的路径，且这条路径不会通过a，即a不是G的关节点。这与前提a是关节点矛盾。所以，当a是根且是关节点时，它的儿子多于一个。

2、a是根，且有两个或两个以上的儿子a是一个关节点。

在a的两个儿子为根的两颗子树上各取一点，则这两顶点之间的任何路径必经过a。如果存在一条不经过a而连接两点的路径，这该生成树中至少存在一条回路，这破坏了树的性质。所以a是一个关节点。

边双连通图是指不存在移除后就丧失连通性的边的图。据此判定下述问题： 1、点双连通图是边双连通图； 2、边双连通图是点双连通图。 1、不一定。因为存在一种特殊的情况，如下图。

ab

上图是点双连通图，但是在移除边ab后，该图剩余的仅是两个孤立的点，是非连通的。所以上图是点双连通图，但不是边双连通图。

但是对于多于一条边的点双连通图一定是边双连通图。因为既然该图是点双连通图，则每一条边都位于一个双连通分量之中，即每一条边都位于一个圈之中，因此移除任何一条边都不会破坏该图的连通性。

2、不一定。例如下图是边双连通图，但是不是点双连通图，点A是关节点。

A

如果权为负值，Digkstra算法是否可以计算出证却的最短路径 当权为负值时，Digkstra算法不能正确的计算出最短路径。例如下图：

t4s10-10x

源节点为s，首先要考虑的边时st，在将t添加到树上之后，再要考虑的边是tx，将节点x添加到树中。这时如果以x为中间节点，更新树中s到各节点的距离时，会陷入死循环中，因为tx为负值，这样就计算不出s到各节点的最短距离。

试证明当有向图的权值非负时，Digkstra的最短路径算法能正确地计算出从源节点到所有其他节点的最短路径。 证明：假定使用Dijkstra算法按照V0,V1,现要证明在k次循环后，可以得到V0,V1,,Vn1的顺序将节点添加到树上（其中V0＝s）。

,Vk的最短路径，且在该树中所有节点到达s节点

的距离都是最短的。由此就可证明在k＝n-1时，所得到的路径都是最短的。

1、当k=0时，最短路径是从V0到V0，d(s,s)＝0，距离最短。

2、当k>0时，假定当k-1时命题成立，现证明在k时也成立。根据前提假设，当前的树包含节点V0,V1,,Vk1。现假定在第k次循环时，当前考察的边时tVk。因为当前的tVk是最

小的，这时从s到达Vk的距离d(s,t)＋W(tVk)是从s到Vk的距离最短的。然后根据算法要求会以Vk为中间节点，更新树中节点集合V0,V1,V0,V1,,Vk中的距离。这时得到的包含节点

,Vk1的树中的节点到达s的距离都是最短的。所以在第k次循环原命题也成立。

综合1和2，使用Dijkstra在n次循环之后，所得到的路径是所有节点到达s节点距离最短的。

如何根据Dijkstra算法得到的parent数组得到从s到指定节点z的最短路径。 假定根节点为s，需要为s，s对应的parent数组中的字段为null，且z节点的序号为z，求得的路径以链表的方式返回，链表中存储的路径以节点的序号表示。

LinkList getShortPath(int[] parent, int z) { Create(LinkList, L); Insert(k, L);

while (parent[z] != s) { Insert(parent[z], L); z = parent[z]; }

Insert(s, L); return L; }

假定要查找图G中从节点s到w的最短距离，但是距离的长度仅是简单的计算从s到w的边的数目。在这里可以使用那种策略来计算这个最短距离更好一些 当然可以使用Dijkstra算法计算，将其中的权都设置为1。但是利用Dijkstra算法会增加很多不必要的计算过程。根据在第七章中我们知道，以s为源节点对图G进行宽度优先搜索所得到的树，从根节点到其他各节点的距离（经过边的数目）是最短的，所以可以使用该方法计算s到w的最短距离。从s节点开始进行宽度优先搜索，在碰到w节点后退出。这时形成的搜索树的根节点（s）到节点w的路径即为最短路径。

修改例子计算Fibonacci数的过程，仅用一个常整数的工作空间，并且在(n)内的时间内计算出Fn。

if (n<=1) return n; prev2 = 0; prev1 = 1;

for (i = 2; i<=n; i++) { cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }

return cur;

假定矩阵A，B，C和D的维数分别为20×2，2×15，15×40和40×4，现要计算A×B×C×D的最佳相乘顺序。根据算法和写出其中的cost，last和multOrder。 C44=0; L44=-1 C33=0; L33=-1;

C34=C33+M(3*4)=15×40×4＝2400; L34=3;

C22=0; L22=-1;

C23=C22+M(2*3)=2×15×40＝1200； L23=2;

C24=min{C22+C34+M(2*(3*4))=0+2400+2*15*4=3600;

C23+C44+M((2*3)*4)=1200+0+2*40*4=1520;}=1520; L24=3; C11=0; L11=-1;

C12=C11+20*2*15=600; L12=1

C13=MIN{C11+C23+20*2*40=1200+1600=2800;

C12+C33+20*15*40=600+12000=12600}=2800;

L13=1

C14=MIN{C11+C24+20*2*4=0+1520+160=1680;

C12+C34+20*15*4=600+2400+1200=4200; C13+C44+20*40*4=2800}=1680

L14=1 COST 0 600 0 2800 1200 0 1680 1520 2400 0 LAST -1 1 -1 1 2 -1 1 3 3 -1 LAST(1,4)=1; LAST(2,4)=3; LAST(2,3)=2;

multOrder=[.,2,3,1]

构造一个含有3个或4个矩阵相乘的例子，该例子在最坏相乘顺序下的乘法次数是最好相乘顺序下乘法次数的至少100倍。 构造矩阵A，B和C，它们的维数分别是100×1，1×100和100×1。

在默认情况下，A×B×C的乘法次数为（100×1×100）＋（100×100×1）＝20000次。 计算cost和last后的乘法顺序为：

cost 0 10000 0 200 100 0 -1 1 -1 last 1 2 -1 multOrder=[.,2,1] A×（B×C）乘法次数为 100×1×1＋1×100×1＝200次。

假定各元素的查找概率分别为A（.20），B（.24），C（.16），D（.28），E（.04）和F（.08），要得到最优二分查找数，给出根据算法和计算得到的数组cost和root，及最优二分查找树。 cost数组和root数组：

1 2 3 4 5 6 7 0 0 1 0 2 0 COST数组 3 0 4 0 5 0 6 0 0 -1 1 1 -1 2 2 2 -1 ROOT数组 3 2 2 3 -1 4 2 3 4 4 -1 5 2 3 4 4 5 -1 6 2 4 4 4 6 6 -1 因为root(1,6)=2;root(3,6)=4;root(5,6)=6，所以最优二分查找树为：

BADCFE

假定算法中比较的键为K1,,Kn，概率为p1,,pn。根据该算法计算出的root数组，

给出构造二叉树的算法。数据结构为BinTree。（该算法应该是O(n)的）。

调用方式为T＝buildBST(1, n);

BinTree buildBST (int first, int last) { BinTree ans;

if (last < first) ans = nil; else {

int k = root[first][last];

BinTree leftSubtree = buildBST(first, k-1); BinTree rightSubtree = buildBST(k+1, last); ans = buildTree(Kk, leftSubtree, rightSubtree); }

return ans; }

描述使用贪心法构造最优二分查找树的策略。该策略总是可以产生最优的二分查找树么举例说明。 假定键的排列顺序为first到last。贪心法的策略是首先在范围first到last内，找到概率最大的键（索引为k），并以该键作为根；然后以相同的策略递归的在first到k-1的范围内构建它的左子树，在k+1到last的范围内构建它的右子树。

贪心算法并不可能总是构造出最优的二分树，而仅仅可以在较短的时间内，用较简单的算法得到一个不算太坏的二分树。因为利用贪心算法可能得到一个链。