计算机算法经典试题参考解答

解：假设A中元素个数为n,B中元素个数为m. 1. 算法思想：输入两个序列A、B

a.分别对A、B进行归并排序 b.同时扫描A、B,设两个指针分别指向A、B的当前扫描元素。初始时i、j分别指向A[0]、B[0]

c. 若A[i]< B[j]则将A[i]存入C中，i后移 若A[i]>B[j] 则将B[j]存入C中，j后移

若A[i]= B[j] 则同时将i、j后移，直到分别出现与其前一个元素值不同的元素为止。 d 重复c直至A、B同时扫描完或某一个扫描完，此时将另一个序列所有剩余元素直接 插入C中即可。

归并排序的时间复杂度为O(nlog2nmlog2m),扫描的时间复杂度为O(nm)，总的时间复杂度为O(nlog2nmlog2m)。

2书后习题4.8

a. How many key comparisons would be done in the worst case? b. How many times are elements moved in the worst case? c. What is the asymptotic order of the worst-case running time?

d. Can the number of moves be reduced by putting the elements in a linked list instead of an array? Explain.

答案：a. log2i1； b. i+2次; c. O(i)

d. 采用链式存储结构可以减少移动次数，但这种结构不能使用折半查找。

3输入n个元素，输出其不同元素。（O(nlogn)）

答案：n个元素保存在数组E[n]中；

(1) 对E[n]进行排序(归并等时间复杂度为O(nlog2n)的算法); (2) 直接输出E[0];

(3) FOR i=1 TO n-1, 如果(E[i]==E[i-1]) 忽略该元素;否则输出E[i]。

4 给出最坏情况下，只需7次比较的5个元素的排序算法

答：假设5个元素为a1，a2，a3，a4，a5 1.对a1,a2,a3,a4进行3次比较

a4a2a4

若a3>a4,a3和a4对换；若a1>a2,a1和a2对换；若a2>a4,a2和a4对换且a1和a3对换. 生成序列为

a1a2a3a4a1a2a3a4

2.将a5插入以上序列（用折半查找思想，共需2次比较）结果可能为：

a5a1a2a3a4a1

a2a5a3a4

a1a5a2a3a4

a1a2a3a4a5

3.将a3插入到以上四种可能，用折半查找，最多需要2次比较 由1、2、3得，此方法只需7次比较。

5 输入n个元素，输出其和为m的全部整数对。

答：首先对n个元素按升序排序，对排好序元素设置首尾两个指针low,high,当low如果E[low]+E[high]=m,则; low++;high--,输出数对 如果E[low]+E[high]m, high— 当Low==high时，程序结束。

6输入n个元素，输出其包含的最长等差数列。

定义三元组e(d,i,j)，其中i、j为元素标号且i(3) 对于所有具有相同公差d的三元组{e1(d,i1,j1),e2(d,i2,j2)}，查找“最长链”

iajaibjbicjx1ixjx，就可以找到公差为d的最长的等差数列iaibixjx，长度为x1。具体方法如下：

e_start，e_end分别记录具有同一公差的三元组在E[K]中的起始、终止位置，初始e_start=1，e_end=-1。

顺序遍历有序的三元组数组E[K]中每一个三元组et(dt,it,jt)，其中t从2开始

如果dtdt1且tK，那么继续遍历下一个三元组； 否则，如果tK置e_end=t-1；如果tK置e_end=t；

并对E[K]中标号从e_start到e_end的三元组

{ee_start(de_start,ie_start,je_start),,ee_end(de_end,ie_end,je_end)}执行找 “最长链”的操作，找出的最长链iaibixjx长度为x1， 如果x1max，则maxx1并将iaibixjx保存到result

中。之后，置e_start=t。

查找{ee_start(de_start,ie_start,je_start),,ee_end(de_end,ie_end,je_end)}中“最长链”方法如下：

数组next[n]，next[i]初始值为-1，最终记录元素i应该链接的下一个元素的标号；

数组label[n]，label[i]初始为false，记录每一个元素是否已经被访问过。

顺序遍历E[k][]中的每一个元组et(dk,it,jt)，如果next[it]为-1，则next[it]jt；否则，继续遍历下一个三元组。

从当前未被遍历的最小下标s开始遍历，直到所有元素都被遍历过，执行操作：

如果next[s]是-1，那么label[s]=true，记录下整数对(s,1)； 否则执行

start=s,counter=1；

执行操作label[s]=true，s=next[s]，counter++，直到next[s]是-1为止； 记录下整数对(start,counter)。

综上，counter值最大的整数对中的start值，就是

{ee_start(de_start,ie_start,je_start),,ee_end(de_end,ie_end,je_end)}中最长的等差数列的

]next[next[start]]...end， 起始位置，对应的最长链为startnext[start其中next[end]=-1。

7.归并排序的优点及优化措施.

答:

基于比较的排序算法平均时间复杂度A(n)O(nlog2n)与最坏时间复杂度

W(n)O(nlog2n)。

证明：对于n个元素来说，判定树的叶子数为n!，其高度对应最深叶子的深度，而最

深叶子的深度对应最坏时间，即若要证明最坏时间O(nlog2n)，就要证明高度

O(nlog2n)。

判定树高度为0时，叶子数20 =1。 判定树高度为1时，叶子数21 =2。

假设高度h的判定树，有2h 个叶子，那么高度为h+1的判定树，左子树高度h，叶子数2h 。右子树高度h，叶子数2h ，于是高度为h+1的判定树叶子数2h +2h =2h+1 。 所以高度为h的判定树，叶子数2h ，因而叶子数为n!的判定树高度log2(n!)。 所以比较排序的最坏时间W(n)判定树的最大高度log2(n!)。

log(n!)log2iinn11n11log2xdxlnxdx[nlnn(n1)]nlogn(n1)O(nlog2n)2ln21ln2ln2

比较排序的平均时间A(n)=判定树的平均叶子深度。 判定树的平均叶子深度：

1n!11n!11A(n)h(i)log2(n!)..log2(n!)log2(n!)nlog2nO(nlog2n)n!i1n!i1n!222推导说明: 叶子数为n!的判定树高度log2(n!)，当判定树高度log2(n!)1时，至多有

n!2n!n!(n!)个叶子，因此在高度log的判定树中，至少有个叶子结点的深度至少为222log2(n!)。第一次放缩时，将深度小于log2(n!)的叶子结点的深度都缩为0，只考虑剩

余的深度为log2(n!)的

n!个叶子结点。 2归并排序算法时间复杂度分析 最坏情况

采用归并排序算法对n个元素排序，在一趟归并操作中，要进行的比较次数至多为n-1，

合并操作的公式为，n表示元素的个数，有

WnW(n/2)W(n/2)n1

可以递归推导得

W(n)nlognlogn(logn1)/2

即

W(n)(nlogn)。

所以归并排序优点为:平均时间与最坏时间都达到了排序的最好指标，速度快。 归并排序改进方法：

1）：与插入排序相结合 2）：无逆序 3）：不递归 4）：不回写

具体改进的算法描述：

将原数据集合分成若干组，分组策略如下：

第一组：从第1个元素a1开始到第20个元素a20，用插入排序排成有序集，从第21个元素起，按无逆序原则向后找到第一个出现逆序的元素ak1为止。那么第一组的元素为

a1,a2…a20…ak.

第二组：从ak1开始按照找第一组的方法，找出第二组;

第三组、第四组……依次类推。

按此方法将数据集分成若干组，在分组的过程中体现出与插入排序相结合和无逆序的改进。 对划分的组进行如下处理：

假定初始的元素存放在数组A中，申请同样大存储空间的数组B。 奇数趟归并排序时（此时元素存储在数组A中），从前向后，两两相邻的分组归并后存放到数组B。

偶数趟归并排序时（此时元素存储在数组B中），从后向前，两两相邻的分组归并后存放到数组A。

重复上述操作，直到最后归并到成一个集合为止。

按此方法对组进行归并排序，体现了不回写和不递归的改进。

8 对一个数值在(1,100)之间的数组进行排序，假设共有n个元素。 （1）试给出基数排序的空间消耗，桶数，总需要时间。

（2）给出在基数排序过程中找出n个元素（n>10）前10个最大的算法思想。

答：

（1）桶的个数m（如m取100）,此时只需一次装桶倒桶完成排序。n个元素需要n个空间存放，还需要n个链表（2n）空间，因此总共需要（3n+m）个空间。清桶的时间复杂度为O(m)；在元素插入链表时，将元素插入链头，这样插入的时间为O(n)；然后倒桶的时间复杂度为

O(nm)，所以基数排序所需的时间为O(nm)。

（2）算法： 1 清桶

2 把a0，a2，„an-1依次装桶，不考虑相同元素被选出的前后顺序。 3从最大的桶开始，依桶的序号递减依次倒桶，直至够10个元素为止。

9 给出n个元素中选最大最小元素的好的算法，并解释好的理由。

答：

(一) 算法：n为偶数，将n个元素的序列分组，每两个元素一组，每组经行比较，一共进行

了n/2次比较，称每组比较后大的那个元素为winner，小的那个为loser，在所有的winner中找一个最大的需n/2-1次比较，再所有loser中找一个最小的需n/2-1次比较，共需

nnn3n112次。 2222n1次比较将最后一2n111个复制为两个，即a[n]=a[n-1]，在所有的winner和a[n]中选一个最大的，需2n111次比较。 次比较，在所有的loser和a[n-1]中选一个最小的需2n1n1n13n3 所以共次比较。 22223n3当n为奇数223n即比较次数2当n为偶数

2n为奇数时，将前n-1个元素两两比较，选出winner和loser，需

(二)①假定n个元素(n为偶数)互不相同，为确认x为max，y为min。算法必须知道除了x之外其他元素都在一些比较中失败过，除了y外，其他元素都在一些比较中成功过。于是设win，lose各作为一个信息量。

找到max：win对应1个信息，找到min：lose对应一个信息，其余n-2个元素，至少胜利、失败各一次，2(n-2)个信息，故要找到max、min至少需要2n-2个信息量。 ②设状态如下：W：至少在一次比较中胜利，且从未失败过。

L：至少在一次比较中失败，且从未成功过。 WL：有成功、有失败至少各一次。 N：从未比较。 x，y比较时的状态 N,N N,W N,L N,WL W,W W,L W,WL

得到新状态 W,L

W,L 或 WL,W W,L或L,WL W,WL或L,WL W,WL

W,WL 或 W,L W,WL 或 WL,WL

信息量 2

最多2个，最少1个 最多2个，最少1个 最多2个，最少1个 1

最多1个，最少0个 最多1个，最少0个

L,L L,WL WL,WL WL,L

WL,WL 或 L,WL WL,WL 1

最多1个，最少0个 0

因为要最少次比较：必须保证每次得到最多信息量，由此表第一次元素均为N，N比较故经n/2次比较后得n个信息量，共需2n-2个信息量，之后，为保证在任何顺序输入情况下都能得出结果，且最坏情况中每次比较最多得到1个信息，故还需要n-2次比较。故至少需要

n3nn22次。 22

给出n个元素中选最大最小元素的好的算法，并解释好的理由。

答：(一) 算法：n为偶数，将n个元素的序列分组，每两个元素一组，每组进行比较，一共进行了n/2次比较，称每组比较后大的那个元素为winner，小的那个为loser，在所有的winner中找一个最大的需n/2-1次比较，在所有loser中找一个最小的需n/2-1次比较，共需

次。

n为奇数时，将前n-1个元素两两比较，选出winner和loser，需次比较将最后一个复

制为两个，即a[n]=a[n-1]，在所有的winner和a[n]中选一个最大的，需次比较，

在所有的loser和a[n-1]中选一个最小的需次比较。 所以共次

比较。即比较次数

(二) 根据对策论的思想,当最终找到最大元与最小元时,最大元在所有比较中都是胜利者,最小元在所有比较中都是失败者,他们只带了一个信息(胜利或失败),其余的n-2个元素都带有两个信息(胜利与失败).

1.两个不带信息的结点比较,可以产生两个信息

2.带信息的结点与其他结点比较,最多产生一个信息。所以为了使用最少的比较产生最多的信息,第一轮必须由不带信息的结点两两比较,比较次数为n/2,每次比较产生两个信息共产生n个信息,那么还需要产生n-2个信息。这时已经没有不带信息的结点,所以最好情况下最多产生一个信息,那么n-2个信息需要n-2次比较.所以最少比较次数:n/2+n-2。即W(n)=3n/2-2,所以算法达到了问题的最少比较次数。

10 同时找n个元素中最大与次大元素的好的算法，并说明你多给出

算法是好的理由。

解：算法：n个元素的数据结构： Key Flag 0 来自左孩子 Flag= 1 来自右孩子

首先n个元素两两比较取最大者为父节点，并标记来自哪个孩子。再在较大者中两两比较去大者为父节点，并标记来源。以次类推，则根为最大者，根据根的flag值向下找到次大元。

找最大元比较n-1次。有log2n个元素与最大元直接比较过，所以找次大元比较

log2n1次，则总的比较次数为nlog2n2次。

证明：设k为与最大元比较的元素个数，w为权值。设每个元素初始值为1，经过1次比较后，胜利者得到失败者的权值，则最大元Wmax =n。若x与y比较，权值为Wx ，Wy

若x为胜利者： Wx = 2Wy Wx = Wy Wx =Wx +Wy Wx > 2Wy Wx >Wy Wx < 2Wy Wx k

最坏情况时，胜者权值Wi+1≤Wi。故n=Wk≤2Wk-1≤„≤2kW0 =2k 即n≤2 ，

k≥log2n。由于次大元与最大元比较过而与最大元比较过的元素个数为树高，故找次大元比较次数为log2n1，即总的比较次数为：n1log2n1nlog2n2

11． 对于n个元素找中间元素的问题，3、5、7、9、15个元素一组对应的时间复杂度分析

答：

5个元素一组：

设从n个元素中找到指定位置的元素时间为 W(n)。 从n个元素中找中间元素的步骤： 1）：5个元素一组对n个元素分组，一共分 n/5 组，从每一组中的5 中找出中间元素要 6 次比较， 时间总共：n/5*6；

2)：在n/5个组中间元素中再次找中间元素，时间为W(n/5)。 3）：通过1）、2），可粗略的得到元素的分别矩阵，矩阵的左上角的3n/10(3n/5*1/2)和右下角的3n/10(3n/5*1/2)个元素肯定不会是中间元素，排除。中间元素只可能存在于剩下的2n/5（1-3n/10-3n/10）个元素中。 4）：2n/5 个元素与当前中间元素比较，所用时间为 2n/5。比较结果最坏情况下为2n/5个元素均大于或小于当前中间元素。 5）：在2n/5+3n/10中找特定位置的元素，时间为 W(7n/10)。 由此的 W(n)n2n7nn6W()W() 55105 1.6n0.7cn0.2cn 若要使 W(n)cn

则要满足：1.6n0.1cn 即 c16

3个元素一组进行分组时：

参照5个一组的情况，得出如下表达式：

nn2nn3W()W() 33334n21cncn 3334n若使 W(n)cn 则出现 0 于实际不符，故，不可以把元素分成三个一组。

3W(n)

7个元素一组进行分组时：

参照5个一组的情况，得出如下表达式：

W(n)n3n5nn11W()W() 7777512ncncn

77若使 W(n)cn 则要满足：2n1cn 即 c14 7

9个元素一组进行分组时：

参照5个一组的情况，得出如下表达式：

W(n)n4n13nn16W()W() 9918920131ncncn 9189若使 W(n)cn 则要满足：

40203ncn 即 c 9183

15个元素一组进行分组时：

参照5个一组的情况，得出如下表达式：

W(n)n7n11nn31W()W() 1515151538111ncncn 151515若使 W(n)cn

则要满足：

38383 ncn 即 c3151512 输入n个元素，输出m个最小的元素，其中(n>>m)。

(1) 将所有n个元素放在数组A中从第n个位置开始的空间里(作为树的叶子)，之后n个元

素两两一组(A[i],A[i+1])进行比较，使用较小元素的索引作为这两个节点的父亲结点(A[i/2])，之后向上一次建树。这样可以建立起一棵树T，T的内部结点都是索引值，叶子结点保存实际的数值。

(2) 输出当前树T的根节点root指向的单元的值，之后将该单元的值设置成，对树T中

root指向的单元从叶子结点到根结点经过的路径进行调整，使之满足父结点是两个儿子当中值较小者的单元地址。

(3)反复执行第2步，直到找够m个最小元素。

算法的时间复杂度分析：第一次建树并找出最小元素需要n1次比较；之后重复进行(m-1)树的调整并输出树根指向的值，每次调整需要的比较次数为log2(2*n1)1；所以，算法的时间复杂度为O(n1(m1)*log2(2*n1)1)。

13 当需要增大数组时，将当前数组大小乘4（代替乘2），评价在时间和空间的策略。

解：假定在有向序列中插入第（n+1）个元素的时候，触发了双倍复制序列操作。

设当从旧序列中复制一个元素到新序列时的时间消耗为t（在这里设定t为某一固定值）。则在将旧序列复制到新序列的时候需要进行n次传输操作。而这次之

nn前的一次双倍复制操作已经进行了2次传输，再前一次是4，并以此类推。则总的时间消耗为Ti01tn2tn。如果使用四倍复制策略，则总的时间消耗为2innnt,t,t,14416，即Titntn。对于空间消耗，四倍复制策略会分配所需

3i04求空间总量的四倍，而两倍复制策略会分配所需求空间总量的两倍。

14 证明引理6.2

证明：

1. 设RBh树和ARBh树的黑色高度为h。

当h0时，对于RB0树，该树由一个外部结点组成，显然对于上述的定理是成立的。

当h=1时，对于ARB1树，该树由一个内部红结点组成，显然对于上述的定理是成立的。

2. 1假定h>0,对所有0jh的所有j, RBj至少有2j1个内部黑结点，且同时，ARBj1至少有2j12个内部黑结点。现证明RBh至少有2h1个内部黑结点和ARBh1至少有2h12个内部黑结点。

ARBh1的内部黑结点个数

左子树RBh的内部黑结点个数右子树RBh的内部黑结点个数(2h1)(2h1)2h12与此同时，假设RBh有02个高度为h的ARBh子树，则有2个高度为h-1的RBh-1子树。所以RBh的内部黑结点个数

12h222h112h112h12h1

2. 2假定h0，对所有0jh的所有j，RBj至多有4j1个内部结点，

4j11个内部结点。现证明RBh至多有4h1个内部结点且ARBj1至多有24h11个内部结点。 和ARBh1至多有2ARBh1有

2个高度为h

的RBh，其内部结点数

1左子树RBh的内部结点数右子树RBh的内部结点数1(4h1)(4h1)4h112

与此同时，假设RBh有02个高度为h的ARBh子树，则有2个高度为h-1的RBh-1子树。所以RBh的内部结点个数

4hh1112412 4h124h1124h124h114h13对于符合定义的ARBh树和RBh树，由于不允许存在红色结点指向红色结点的边，所以从根到任何黑色结点的路径上，所包含的红色结点数小于或等于黑色结点数，即红色结点数至多为路径上所有结点数目的一半。又因为每一个红色结点被一条非黑色边指向，非黑色边的数目至多为路径上所有边数目的一半，所以“任何黑色结点的深度至多为该结点黑色深度的两倍”。

15 给出Prim算法的时间复杂度和正确性证明，算法描述，程序。

答：

Prim算法基本思想：

假设G=(V,E)是一个具有n个结点的连通图，T=(U,TE)是G的最小生成树,其中U是的结点集，TE是的T边集,U与TE初始值为空。 算法描述：

算法采用三个一维数组: U为顶点访问标志，W为目前到达各点最近距离，B为记录每个结点通过与哪个结点相连的边被并入生成树的顶点集。

(1)从V中任取一个顶点设为v0,将他并入U中,此时U={v0}，初始化 [v0]=1,U[i]=0,W[i]=G[0][i],B[i]=0。

(2)从V-U中选择vj(W[vj]为到U中结点最近距离)，修改U[vj](将vj并入生成树的结点集),并更新从已到达点集到未到达点的最小距离数组W[]及相应的起点数组B[]。

(3)然后只要U中结点个数少于n个，就重复执行步骤(2)。 时间复杂度：

根据W数组，从所有不在U中的点中，选一个距离U最近的点，时间复杂度为O(n)；选取点后，更新未到达点与已到达点连边的权重及起点数组，时间复杂度为O(n)。要对n-1个结点进行以上操作，所以总时间复杂度为O(n)。 代码:

for(i=0;i2 for(i=0;ifor(l=1;lv=-1; for(i=1;iw[i]) { Min=w[i]; v=i;

}

} }

//把找到的点加入已到达点集合，并更新到未到达点的距离 U[v]=1;

for(i=1;icontinue;

if(g[v][i]正确性证明： （1） 引理：对于该算法生成的MST记为T1，与任意e*E(G)且e* T1，有W(e*)>=W(e)，

其中e为把e*添入T1后形成回路中不同于e*的任意一条边。

证明：反证法。 假设T1中存在至少一条边e’，W(e’)>W(e*)。设e=xy为在最小生成树T1中添入e*=st后所构成回路中权值最大的边，有W(e)>=W(e’)>W(e*)。不妨假设A为MST的源点且x先于y，s先于t被添加到MST中，A到x的路径为As1s2…x，A到s的路径为Aw1w2…s。在x被添入T1后，由于e的权重大于环路中的其他边，所以A到s路径上的边会先于e被选入T1。又由于W(e) >W(e*)，因此e*边会被选择进入T1，与假设e*不是MST中的边矛盾。

所以原命题正确。

（2）设由算法得到的MST为T1，假定T2为具有与T1相同边最多的一棵实际上的MST。设e1为算法执行过程中找到的一条在T1且不在T2的最小权值的边。将e1添入T2中，必形成回路，回路中必存在一条在T2不在T1中的边,记为e2，删除e2得T2’。将e2添入T1中，e3为所形成回路中不在T2中的边，

若:①w(e1)②w(e1)=w(e2),T2’与T1具有相同边数比T2与T1具有相同边数多1，与T2有相同边数最多的假设矛盾；

③w(e1)>w(e2), 由引理W(e2)>=W(e3),得W(e1)>W(e3).与e1为在T1且不再T2中权最小的边矛盾。

所以，Prim算法执行过程是正确的。

16 给出Kruscal算法的算法描述，时间复杂度和正确性证明，程序。

(1)算法思想：设G=(V,E)是一个具有n个顶点的连通图，T=(U,TE)是G的最小生成树。U的初值等于V，包含G的全部顶点，算法开始时，TE为空集。

预处理：①先将G中边按权值从小到大排序(O(mlogm))；②然后建立以每个结点为根的一

棵只有一个结点的树，父结点均为空，同时记录结点个数为1。

合并：在排好序的边中，依次选取每一条边e，查找e两个结点所在树的树根过程中，把沿途各点改为根的儿子。若这两个结点所在树根不等，则不会形成回路，把结点数少的子树根结点作为另一棵子树的儿子（若结点数相等，默认前者为后者儿子），同时修改树的大小。若两个结点所在树根相等，则添加后会形成回路，舍弃e，选取下一条边，如此进行下去，直到找到能用的 n-1条边为止。

(2)时间复杂度：该算法用可并堆实现。首先把所有边按权值大小排序O(mlogm)，依次考察所有边。每次主要做两个工作即移动顶点与合并。合并时，只把小树根改为大树根的儿子，代价为O(1)；移动顶点即在查找树根过程中，把结点到他所在树根途中的点都改为根的儿子，每个结点的父结点最多被修改logn次，n个结点最多不超过nlogn。所以时间复杂度不超过O(nlogn)。 (3)代码:

(4)正确性证明:

（1）引理：对于该算法生成的MST记为T，与任意eE(G)且e T，有W(e)>=W(e)，其中e为把e添入T后形成回路中任意一条边。

证明：反证法

在算法生成的最小生成树T中任添一条不在其中的边e*后则构成回路。假设e*不是回路中权值最大的边，则回路中存在权值大于W(e*)的边。设边集合：E1={e|e在T中且W(e)>W(e*)}；E2={e|e在T中且W(e)综上所述，往计算机生成的MST中添加任意一条不在其中的边e*，则e*在所构造回路中权值最大。

（2）设由算法得到的MST为T1，假定T2为具有与T1相同边最多的一棵实际上的MST。

''设e1为算法执行过程中找到的一条在T1且不在T2的最小权值的边。将e1添入T2中，必存在回路，回路必存在一条在T2不在T1中的边,记为e2，将e2添入T1中，e3为所形成回路中不在T2中的边，

①若W(e1)②若W(e1)=W(e2),与T2与T1具有相同边数最多矛盾;

W(e1)>W(e2).由引理W(e2)>=W(e3),得W(e1)>W(e3).与e1为在T1且不再T2中权最小的边矛盾。

所以Kruscal所得生成树为最小生成树。

17 给出Dijstral算法的时间复杂度和正确性证明，算法描述，程序。

Dijstra思路:设有向图G=(V,E)，其中V{V0,V1,,Vn1}，cost是邻接矩阵，cost[i][j]表示之间权值，若不存在；cost[i][j]= ，一维数组S[0—n-1]标记找到最短路径上的点。设有V0,S初态，只包含V0，即

Wij(ViVj且E(G))cost[i][j]0(ViVj)

(其它)0未找到原点到顶点Vi的最短路径S[i]

1已找到原点到顶点Vi的最短路径Dist[i]记录从源点到其他各点当前最短距离，从S外的集合V-S中选出一个点Vu，使Dist[u]值最小，于是从源点到Vu只通过S中的顶点，把u加入S中，调整集合dist[]中的值（从源点到v-s中所有点的距离）,从原来的dist[j]与dist[u]+cost[u][j]中选择最小的值，更新dist[j]。重复上述过程，直到S中包含其余各顶点.

时间复杂度：算法每次从V-S中选j，使dist[j]最小，这个过程最多检查n-1个值，重复n-1次，所以时间复杂度为O(n)

核心代码：

把Prim代码中加//*行改为 if(g[v][i]+w[v](4)正确性证明：

假定计算机算法求出的从A到X的路径不是实际的最短路径，那么在这条路径上一定有一些出错的点O1O2„，O1为第一个出错的位置。

设计算机算法给出的由A到O1的路径为Py=Ay1„yt O1，而实际的最短路径为Pz=Az1„zsO1 。 如果ytzs，那么W(Az1„zs)2若yt 先到达，当Zs到达时，由于W(Pz)若zs先到达，在到达O1时，要么建立路径Pz，要么事先已经建立了一条与Pz一样短的路径 P'z(对应由A到O1存在不止一条最短路径的情况)，而当yt到达时，由于W(Pz)因此，不会出现计算机算法给出的路径Py，与计算机算法输出了路径Ay1„yt O1矛盾。 综上所述，假设不成立。即计算机找到的路径是A到X的最短路径，Dijkstra算法正确。

18 给出Floyd算法的时间复杂度和正确性证明，算法描述，程序。

答：

算法描述：

(1) 用数组dis[i][j]来记录i,j之间的最短距离。初始化dis[i][j],若i=j则dis[i][j]=0, 若i,j之间有边连接则dis[i][j]的值为该边的权值，否则dis[i][j]的值为。 (2) 对所有的k值从1到n，修正任意两点之间的最短距离，计算dis[i][k]+dis[k][j]的值，

若小于dis[i][j],则dis[i][j]= dis[i][k]+dis[k][j]，否则dis[i][j]的值不变。 程序：

void Floyd(int dis[n+1][n+1],int path[n+1][n+1],int n) { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dis[i][k]+dis[k][j]{

dis[i][j] = dis[i][k]+dis[k][j];

Path[i][j]=k; }

}

正确性证明(归纳法) ：

对于任意两点A，B：

（1） 当从A到B之间的最短路径，在中间没有经过顶点或经过1个顶点号为1

的顶点时，算法显然正确。

（2） 假设A到B经过的最大顶点号不超过k-1时，算法得到的最短距离是正确

的

（3） 当A到B经过的最大顶点号为k时，则从A到顶点号为k的顶点vk之间

的顶点号均不大于k-1，从vk到B之间的顶点号也不大于k-1，由假设2得，A到vk的距离是中间顶点号不超过k-1的最短距离，vk到B的距离是中间顶点号不超过k-1的最短距离，所以A经vk到B为A，B之间经过最大号为k的路径中距离最短的，由算法修正A，B的最短距离，即可得到A，B间顶点号不超过k的最短距离。

（4） 综上所述，算法是正确的 时间复杂度：O（n3）

19 n*n的棋盘，从左下角A至右上角B不超过主对角线的走法有多少种，并证明。

走法有

1Cn2n种。 n1证明：

设B'是B关于次对角线的对称点，A到B'的任意一种走法对应A到B过对角线的一种走法：

（1） 由A->B,共有x=C2n种走法 （2） 由A->B'共有w=C2n种走法

（3） 设由A->B，超过主对角线的走法有y种

（4） 设由A->B，不超过主对角线的走法有z种，z=x-y

（5） 因为A与B'分别处在次对角线的两侧，所以，所有的从A->B'的走法都必然

要超过次对角线，将其任意一种走法中第一次碰到次对角线之后的部分关于次对角线对称过来，就可以得到A->B超过主对角线的一种走法，故wy.

将从A->B过主对角线的任意一种走法中第一次碰到次对角线之后的部分关于次对角线对称过去就可以得到A->B'的一种走法，故yw. 所以y=w。

n-1nz=x-y=x-w=

n󰀀1CnC22n󰀀n(2n)!(2n)!(2n)!(2n)!(2n)!n1󰀀󰀀(1󰀀)Cn2nn!n!(n󰀀n1n11)!(n1)!n!n!n!n!(n1)n!n!

20 给出拓扑排序算法，并给出时间复杂度。

算法：

把图中节点的状态分成三种。white代表节点还未被搜索到，gray代表节点已被搜索到但还未被处理完，black代表节点已被处理完。数组topo[]来记录每个顶点的编号。

（1） 把图中所有的节点的状态初始化为white，topoNum=n,从顶点号为1的顶点

开始搜索color[1]=gray.

（2） 设当前搜索到的节点为v，则按深度优先的方式搜索它的邻接点，若存在

某个邻接点状态为white，则把该邻接点的状态改为gray，把它作为当前搜索到的节点，继续按深度优先方式搜索；若所有的邻接点状态都不是white则把当前节点状态改为black，topo[v]=topoNum,topoNum--,然后退回到上一个节点。若在搜索过程中遇到顶点颜色为gray,说明有环路,程序退出。

（3） 当所有节点的状态都为black时，退出循环。 时间复杂度：

设顶点数为n，边数为m。

算法分为两部分：初始化和搜索节点，显然初始化的时间复杂度是O（n），搜索 节点则是按按深度优先的方式查找所有的边，时间复杂度为O（m+n），故此时间 复杂度为O（m+n）。

基数排序（。。。） 5个、7个。。。 找中间元素 杂凑表（）

红黑树（插入、删除） 动态规划（矩阵、棋盘、） 拓扑排序 删除指令

决策论（）

归并排序的优化。。。 排序的复杂度（证明）

四个（2个）

最大次大 前k个元素