华中科技大学《算法设计与分析》复习参考题

1．什么是算法？算法必须满足的五个特性是什么？

算法：一组有穷的规则，规定了解决某一特定类型问题的一系列运算。（有限指令的集合，遵循它可以完成一个特定的任务）.

必须满足的五个特性是(遵循以下五条准则)： 1．有穷（限）性 2．确定性

3．可（能）行性 4．输入（n≥0） 5．输出（n≥1） 2．对算法进行分析分哪两个阶段？各自完成什么任务（分别得到什么结果）？

对一个算法要作出全面的分析可分成两个阶段进行，即：事前分析和事后测试。

事前分析求出该算法的一个时间界限函数；

事后测试搜集此算法的执行时间和实际占用空间的统计资料。

3．证明：若f1(n)=O(g1(n))并且f2(n)= O(g2(n))，那么f1(n) +f2(n)= O(max{g1(n), g2(n)}

证明：

根据f1(n)=O(g1(n))可知，存在正常数C1，当n≥n0时，使得|f1(n)|≤C1|g1(n)|； 同理，根据f2(n)= O(g2(n))可知，存在正常数C2，当n≥n0时，使得|f2(n)|≤C2|g2(n)| 当n≥n0时，|f1(n)+f2(n)|≤|f1(n)|+|f2(n)|≤C1|g1(n)|+C2|g2(n)| ≤C1|gk(n)|+C2|gk(n)|

≤（C1+C2）|gk(n)|， 其中gk(n)=max{g1(n),g2(n)}，k={1,2}

当n≥n0时，取C=（C1+C2），据定义命题得证。

4．如果f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n))，下列说法是否正确？试说明之。

（a） f1(n) +f2(n)= Θ(g1(n)+ g2(n))

（b） f1(n) +f2(n)= Θ(min{g1(n), g2(n)}) （c） f1(n) +f2(n)= Θ(max{g1(n), g2(n)}) 答：（a）和（c）均正确，（b）错误。

（a）正确可以根据定义直接证得。

（b）错误可举反例。例：f1(n)= 2n，f2(n)=2 n2 下面证明（c）正确性.

根据上题已经证明f1(n)+f2(n)= O(max{g1(n),g2(n)})，下面只需证明f1(n)+f2(n)= Ω(max{g1(n), g2(n)})，即存在正常数C，使得|f1(n)+f2(n)|≥C(max{g1(n), g2(n)})

根据f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n)) 得到，当n≥n0时，存在正常数C1、C2 、C3、C4

C1|g1(n)|≤|f1(n)|≤C3|g1(n)|

C2|g2(n)|≤|f2(n)|≤C4|g2(n)|

不妨设max{g1(n), g2(n)}= g1(n)

由于|f1(n)+f2(n)|≥||f1(n)|-|f2(n)||≥|C1|g1(n)|-C3|g2(n)||

=C|max{g1(n), g2(n)}|

取C≥|C1-C3|的正常数，由定义得 f1(n)+f2(n) = Ω(max{g1(n), g2(n)}) 命题得证。

5．证明 |「log2n」|= O(n)

证明：对于任意的正整数n，

|「log2n」|≤|log2（n+1）|≤|n+1|≤2|n| 取n0=1，C=2，根据定义知命题成立。

6．证明 3n「log2n」= O(n2)

2

证明：对于任意的正整数n，|3n「log2n」|≤|3n「log2n」|≤3|n| 取n0=1，C=3，根据定义知命题成立。

n7．用数学归纳法证明：当n≥1时，?i?n(n?1)/2.

i?1n证明：当n=1时，?i?1，n(n+1)/2=1，命题成立；

i?1n 假设n=k-1时，?i?n(n?1)/2成立;（k≥2）

i?1nn 当n=k时，?i?n(n?1)/2=?i?k(k?1)/2?k=k(k+1)/2

i?1i?1综上可知，命题成立。

8．在下列情况下求解递归关系式

?g(n)n足够小 T(n)= ?

否则?2T(n/2)?f(n)

当①n=2k g(n)= O(1)和f(n)= O(n)；

k

②n=2g(n)= O(1)和f(n)= O(1)。

解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) =??

=2kT(1)+2k-1f(2)+2k-2f(22)+?+20f(2k) =2kg(n)+ 2k-1f(2)+2k-2f(22)+?+20f(2k) ①当g(n)= O(1)和f(n)= O(n)时，

不妨设g(n)=a，f(n)=bn，a，b为正常数。则

T(n)=T(2k)= 2ka+ 2k-1*2b+2k-2*22b+?+20*2kb =2ka+kb2k

=an+bnlog2n= O(nlog2n)

②当g(n)= O(1)和f(n)= O(1)时，

不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+?+20d=c2k+d(2k-1)

=(c+d)n-d= O(n)

9．求解递推关系式：

h(n)?2h(n?1)?1

解：构造生成函数

H(x)?h(1)x?h(2)x???2h(1)?1?h(k)x

kk?1?求解H(x)

H(x)?h(1)x?h(2)x???2xH(x)??2h(1)x?2h(2)x??232

x (1?2x)H(x)?x?x2?x3???H(x)?x(1?2x)(1?x)1?x (x?1)

分解H(x)成幂级数 令H(x)?

?H(x)??11?x?11?2x2A1?x?B1?2x 则A=-1 B=1

??(1?x?x??)?(1?2x?(2x)?(2x)??)2nn223

?(2?1)x?(2?1)x???(2?1)x??

???(2k?1k?1)xk

所以?h(n)?2n?1

?T1?110．求解递推关系式：?

T?2T?2n?1?n解：

Tn?2Tn?1?2?2(Tn?2?2)?2?2Tn?2?2?2?222n?1T1?(2n?1???2)?3*2n?1?2

?F1?1?11．求解递推关系式：?F2?1

?F?F?F(n?2)n?1n?2?n解：以Fn为系数，构成生成函数F(x)

F(x)?F1x?F2x??2 xF(x)?F1x?F2x???xF(x)?F1x?F2x??23423

(1?x?xF(x)?F1x?(F2?F1)x?(F3?F2?F1)x???xF(x)?x1?x?x22)23?(x??x1?25)(x?1?25)?x?A1?25?x?B1?25

A?12(?1?15) B?12(?1?15)

F(x)?15((???)x?(?222??)x??

其中??15151?2n5 ??1?25

Fn?(?n??)52

Fn?n??(1?

)n

12．分治法的三个步骤是什么？给出使用SPARKS语言描述的分治策略抽象化控制。

答:分治法的三个步骤是: ① 分解 ②解决 ③合并 用SPARKS语言描述的分治策略抽象化控制为:

Procedure DANDC(p,q)

Global n,A(1:n);integer m,p,q; If SMALL(p,q)

Then return(G(p,q)) Else m←DIVIDE(p,q)

Return(COMBINE(DANDC(p,m), DANDC(m+1,q)))

Endif End DANDC

13．根据教材中所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid

if low≤high then

mid←?(low?high)/2?

if x=A(mid) then j←mid; endif

if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

14．作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。

Procedure ThriSearch(A, x, n, j)

integer low, high, p1, p2 low←1; high←n while low≤high do

p1←?(2low?high)/3? ; p2←?(low?2high)/3?

case

:x=A(p1): j←p1; return :x=A(p2): j←p2; return :xA(p2): low←p2+1

:else: low←p1+1; high←p2-1

end case

repeat j←0

end ThriSearch

?g(n)T(n)= ??T(n/3)?f(n)

n足够小否则

g(n)= O(1) f(n)= O(1) 成功:

O(1),

O(log3(n)), O(log3(n))

最坏

最好， 平均，

失败:

O(log3(n)), O(log3(n)), O(log3(n)) 最好， 平均， 最坏

15．对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。 证明：数学归纳法

①当n=1时，易知E=2，I=0，所以E=I+2n成立； ②假设n≤k(k>0)时，E=I+2n成立；

③则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展

树的定义，一定存在这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除，生成新二元扩展树。此时新二元扩展树内部结点为k个，则满足Ek=Ik+2k，考察原树的外部路径长度为Ek+1= Ek-（h-1）+2h，内部路径长度为Ik+1=Ik+（h-1），所以Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1)，

综合①②③知命题成立。

16．以比较为基础（基本操作）的分类算法最坏情况的时间下界是什么？ 答： ?（nlogn）

17对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是什么？简要说明理由。 答： ?log(n?1)?

对线性存储的有序表中元素的以比较为基础的检索算法的执行过程都可以用二元判定树来描述。该树的每个内结点表示一次元素比较，因此对检索的最坏情况而言，该树最少含有n个不同的内结点。检索算法最坏时间不大于该树中由根到一个叶子的最长路径长（树高）。对有n个结点的二元树其最小树高为

?log(n?1)?，所以对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是?log(n?1)?。

18．简要说明选择问题算法中二次取中值规则的作用。

答：通过选择划分元素V使其尽量靠近元素集合的中间可以得到一个最坏情况时间复杂度是O（n）的选择算法。使用二次取中值规则可以选出满足要求的划分元素V。

19．给出斯特拉森矩阵乘法算法执行时间的递归关系式，并对其求解计算时间复杂度。

答：斯特拉森矩阵乘法算法执行时间的递归关系式为：

?bn?2 T(n)= ? 2n?2?7T(n/2)?an其中a和b是常数。

求解这个递归式，得

T(n)?7[7T(n/4)?a(n/2)]?an?7T(n/4)?an(1?7/4)

2222

?7[7T(n/8)?a(n/4)]?an(1?7/4)

222?7T(1)?an[1?7/4?(7/4)?...?(7/4)?7?an[(7/4)?1]/(7/4?1)k2kk22k?1]

?(c?1)7?(c?1)nk

log7?O(n?O(nlog7) )

2.8120．通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。

P=(A11+A22)(B11+B22) T=(A11+A12)B22

Q=(A21+A22)B11 U=(A21-A11)(B11+B12) R=A11(B12-B22) V=(A12-A22)(B21+B22) S=A22(B21-B11) C11=P+S-T+V

=(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22) =A11B11+A22B11+A11B22+A22B22+A22B21

-A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22 =A11B11 +A12B21 C12=R+T

= A11B12-A11B22 +A11B22+A12B22 = A11B12 +A12B22 C21=Q+S

= A21B11+A22B11 +A22B21-A22B11 = A21B11 +A22B21 C22=P+R-Q+U

=(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12) =A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12 -A11B11-A11B12 =A22B22+A21B12

21．过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？

最好情况：是对有序文件进行排序。

分析：在此情况下归并的次数不会发生变化----log(n)次

归并中比较的次数会发生变化（两个长n/2序列归并）

最坏情况

两个序列交错大小，需要比较n-1次

最好情况

一个序列完全大于/小于另一个序列，比较n/2次

差异都是线性的，不改变复杂性的阶

因此最好情况也是nlogn, 平均复杂度nlogn。 可以说归并分类的时间是Θ(nlogn)

22．写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。 答：见《数据结构》

算法MPass（R，n，1ength．X）

MP1 [初始化]

i?1 ．

MP2 [合并相邻的两个长度为length的子文件]

WHILE i ≤ n – 2*length + 1 DO

（Merge（R，i，i＋length–l，i＋2*length–1．X）. i?i＋2*length ） ．

MP3 [处理余留的长度小于2*length的子文件] IF i+length–1 < n

THEN Merge（R，i，i+length–1，n. X）

ELSE FOR j = i TO n DO Xj←Rj ▌

算法MSort(R，n) // 直接两路合并排序算法，X是辅助文件，其记录结构与R相同

MS1 [初始化]

length?1 ．

MS2 [交替合并]

WHILE length < n DO

（MPass（R，n，length．X）. length?2*length if length > n

then FOR j = 1 TO n DO Rj←Xj else MPass（X，n，length．R）. length?2*length）

endif )▌

23．什么是约束条件？什么是可行解？什么是目标函数？什么是最优解？并举例说明。

答：有一类问题，解由输入的某个子集组成，但是这个子集必须满足某些事先给定的条件。那些必须满足的条件称为约束条件。

满足约束条件的子集称为可行解。

为了衡量可行解的优劣，事先也给出一定的标准，这些标准一般以函数形式给出，称为目标函数。

使目标函数取极值的可行解称为最优解。

26．什么是贪心方法? 给出使用SPARKS语言描述的贪心方法的抽象化控制。 答：对求取最优解问题，选取一种度量标准，将输入按度量标准排序，并按此序

一次输入一个量。如果这个输入和前面输入产生的在这种度量意义下的部分最优解加在一起产生一个可行解，将其加入形成新的在这种度量意义下的部分最优解；若不能构成一个可行解，则去掉该输入；重复此过程直到将输入枚举完成。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心方法。

贪心方法的SPARKS语言描述的抽象化控制为： Procedure GREEDY(A,n) soltion??

for i?1 to n do x?SELECT(A)

if FEASIBLE(soltion,x)

then soltion?UNION(soltion,x) endif repeat

return(soltion) end GREEDY

24．① 求以下情况背包问题的最优解，n=7，m=15，=(10,5,15,7,6,18,3)（p1,.....p7）（w1,.....w7）和=(2,3,5,7,1,4,1)。

② 将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/ FG(I)是多少?

③ 当物品按wi的非降次序输入时，重复②的讨论。 解：① 按照pi/wi的非增序可得

(p5/w5，p1/w1，p6/w6，p3/w3，p7/w7，p2/w2，p4/w4) = (6,5,9/2,3,3,5/3,1)

W的次序为(1,2,4,5,1,3,7),解为(1,1,1,1,1,2/3,0) 所以最优解为：（1,2/3,1,0,1,1,1）

FO(I)=166/3

② 按照Pi的非增次序输入时得到

(p6,p3,p1,p4,p5,p2,p7)= (18,15,10,7,6,5,3)，

对应的(w6,w3,w1,w4,w5,w2,w7)= (4,5,2,7,1,3,1) 解为(1,1,1,4/7,0,0,0)

所以FG(I)的解为（1,0,1,4/7,0,1,0） FG(I)=47，所以FO(I)/ FG(I)=166/141.

③ 按照wi的非降次序输入时得到

(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7) 相应的(p5,p7,p1,p2,p6,p3,p4)=(6,3,10,5,18,15,7) 解为(1,1,1,1,1,4/5,0)

则FW(I)的解为（1,1,4/5,0,1,1,1） FW(I)=54，所以FO(I)/ FW(I)=83/81.

25．（0/1背包问题）如果将5.3节讨论的背包问题修改成

n 极大化

?px

ii1n 约束条件 ?wixi?M xi=0或1 1≤i≤n

1这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。

证明：当按照pi/wi的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。

可举例如下：设n=3，M=6，（p1, p2, p3）=(3,4,8)，（w1, w2, w3）=(1,2,5)，按照pi/wi的非增序得到（p1/w1, p2/w2, p3/w3）=(3,2,1.6)，则其解为（1,1,0），而事实上最优解是(1,0,1)，问题得证。

26．假定要将长为l1,l2,?, ln的n个程序存入一盘磁带，程序i被检索的频率是fi。如果程序按i1,i2,?, in的次序存放，则期望检索时间（ERT）是

njnik[?(fijj?1?lk?1)]/?fii?1

① 证明按li的非降次序存放程序不一定得到最小的ERT。 ② 证明按fi的非增次序存放程序不一定得到最小的ERT。 ③ 证明按fi/li的非增次序来存放程序时ERT取最小值。 证明：只需证明结论③是正确的即可，现证明如下： 假设li,li12,?, linnn按照fi/li的非增次序存放，即

fi1/li≥fi/li≥?≥fi/li，则得到

122

ERT=[fili+fi(li+li)+?+fi(li+li+?+ li]/?fi

11212n12nni?1假设该问题的一个最优解是按照j1,j2,?, jn的顺序存放，并且其期望检索式件是ERT?，我们只需证明ERT≤ERT?，即可证明按照fi/li的非增次序存放得到的是最优解。易知

ERT?=[fj1lj1+fj2(lj+lj)+?+fj(lj+lj+?+ lj)]/?fi

12n12nni?1从前向后考察最优解中的程序，不妨设程序jk是第一个与其相邻的程序jk?1存在关系fj/lj≤fj/lj，则交换程序jk和程序jk?1，得到的期望检索时间

kkk?1k?1记为ERT??

ERT??-ERT?=fjkljk?1-fjk?1ljk≤0

ERT?? ≤ERT?

显然ERT??也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。命题得证。 27.假定要把长为l1,l2,?, ln的n个程序分布到两盘磁带T1和T2上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在T1和T2上的程序集合分别是A和B，那么就希望所选择的A和B使得max{?i?Ali,?i?Bli}取最小值。一种得到A和B的贪心方法如下：开始将A和B都初始化为空，然后一次考虑一个程序，如果?i?Ali=min{?i?Ali,?i?Bli}，则将当前正在考虑的那个程序分配给A，否则分配给B。证明无论是按l1≤l2≤?≤ln或是按l1≥l2≥?≥ln的次序来考虑程序，这种方法都不能产生最优解。

证明：按照l1≤l2≤?≤ln存放不会得到最优解，举例如下：

3个程序（a,b,c）长度分别为（1,2,3），根据题中的贪心算法，产生的解是A={a,c}B={b}，则max{?i?Ali,?i?Bli}=4，而事实上，最优解应为3，所以得证.

按照l1≥l2≥?≥ln的次序存放也不会得到最优解，举例如下：

5个程序（a,b,c,d,e）长度分别为（10,9,8,6,4）根据题中的贪心算法，

产生的解是A={a,d,e}B={b,c}，则max{?i?Ali,?i?Bli}=20，而事实上，最优解应为19，所以得证。

28.①当n=7，=(3,5,20,18,1,6,30) 和（p1,.....p7）（d1,.....d7）=(1,3,4,3,2,1,2)时，算法5.4所生成的解是什么？

② 证明即使作业有不同的处理时间定理5.3亦真。这里，假定作业I的效益

pi>0，要用的处理时间ti>0，限期di≥ti.

非

增

排

序

得

到

解：①根据

pi的

(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法5.4生成的解为：

a.J(1)=7

b.J(1)=7,J(2)=3

c.J(1)=7,J(2)=4,J(3)=3

d.J(1)=6, J(2)=7,J(3)=4,J(4)=3；

②证明：显然即使ti>0（di≥ti），如果J中的作业可以按照?的次序而又不

k违反任何一个期限来处理，即对?次序中的任一个作业k，应满足dk ≥?tj，

j?1则J就是一个可行解。

下面证明如果J是可行解，则使得J中的作业可以按照di,di,?, di排列

12n的序列?处理而又不违反任何一个期限。

k因为J是可行解，则必存在??=r1r2?rn，使得对任意的rk，都有dk≥?tj，

j?1我们设?是按照di≤di≤,?,≤di排列的作业序列。假设????，那么令a是使

12nra?ia的最小下标，设rb=ia，显然b>a，在??中将ra与rb相交换，因为dr≤dr，

ba显然ra和rb可以按期完成作业。

还要证明ra和rb之间的作业也能按期完成。因为dr≤dr，而显然二者之间

bab的所有作业rt，都有dr>dr，又由于?是可行解，所以?tk≤dr≤dr。所以作

tbbtk?1业ra和rb交换后，所有作业可依新产生的排列???==s1s2?sn的次序处理而不违

反任何一个期限，连续使用这种方法，??就可转换成?且不违反任何一个期限，定理得证。

29．① 已知n-1个元素已按min-堆的结构形式存放在A(1),?,A(n-1)。现要将另一存放在A(n)的元素和A(1:n-1)中元素一起构成一个具有n个元素的min-堆。对此写一个计算时间为O(logn)的算法。

② 在A(1:n)中存放着一个min-堆，写一个从堆顶A(1)删去最小元素后将其余元素调整成min-堆的算法，要求这新的堆存放在A(1:n-1)中，且算法时间为O(logn).

③ 利用②所写出的算法，写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。

解：① procedure INSERT(A,n) integer i, j, k

j←n ; i←?n/2? while i≥1 and A[i]>A[j] do k←A[j];

A[j]←A[i]; A[i]←k

j←i ;

i←?i/2?

repeat end INSERT

② procedure RESTORE(A,l,n) integer i, j, k x←A[n];

A[n]←A[l]

i←1 j←2*i

while j≤n-1 do

if (j< n-1) and (A[j]> A[j+1])

then j←j+1 endif

if (x>A[j])

then A[i]←A[j]; i←j;j←2*i else i←n endif repeat end RESTORE

③ procedure HEAPSORT(A,n) integer i, k

for i=?n/2? to 1 step –1 do

RESTORE(A, i, n) repeat

for i=n to 2 step –1 do

k←A[1]; A[1]←A[i]; A[i]←k RESTORE(A, 1, i-1) repeat

end HEAPSORT

30．① 证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足n mod (k-1)=1.

② 证明对于满足 n mod (k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.

证明：① 设某棵树内部节点的个数是m，外部结点的个数是n，边的条数是e，

则有

e=m+n-1和 e=mk

mk=m+n-1 ? (k-1)m=n-1 ? n mod (k-1)=1

② 利用数学归纳法。

当n=1时，存在外部结点数目为1的k元树T，并且T中内部结点的度为

k；

假设当 n≤m，且满足n mod (k-1)=1时，存在一棵具有n个外部结点的

k元树T，且所有内部结点的度为k；

我们将外部结点数为n(n为满足n≤m，且n mod (k-1)=1的最大值)的符

合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T’中外部结点的数目为n+(k-1)，显然n为满足n mod (k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，即存在符合性质的树。

综合上述结果可知,命题成立。

31．① 证明如果n mod (k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,?, qn）生成一棵最优的k元归并树。

② 当（q1,q2,?, q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。 解：①通过数学归纳法证明：

对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。

假定该算法对于（q1,q2,?, qm），其中m =(k-1)s+1 (0 ≤ s)，都生

成一棵最优树.

则只需证明对于(q1,q2,?, qn)，其中n=(k-1)(s+1)+1，也能生成最优

树即可。

不失一般性，假定q1≤q2≤?≤qn，且q1,q2,?, qk是算法所找到的k

棵树的WEIGHT信息段的值。于是q1,q2,?, qk棵生成子树T，设T?是一棵对于

（q1,q2,?, qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,?, qk，则可以用q1,q2,?, qk和P现在的儿子进行交换，这样不增加T?的带权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T?中如果用其权为q1+q2+?+qk的一个外部结点来代换T，则所生成的树T??是关于(q1+q2+?+qk,qk?1,?,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+?+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于(q1+q2+?+qk,qk?1,?,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,?, qn)的最优归并树。

32．对n=7, ( p1,...,p7)=(35，30，25，20，15，10，5) 和( d1,...,d7)=(4，2，4，3，4，8，3)的有限期作业调度问题使用教材中作业排序的更快算法求解最优解。（要求描述时间片数组F（i）和对应集合的变化过程）

33．当作业数n＝7，

（p1，p2，??，p7）＝（7, 6, 5, 4, 3, 2, 1） （d1，d2，??，d7）＝（4, 2, 4, 3, 1, 4, 6）

时，利用算法5.5（作业排序的更快算法）求解上述作业排序问题的最优解。（要求按步骤运行并给出集合树的变化情况及当前最优解）。

34．举例说明最优性原理是什么？

最优性原理是指，过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。

例如：

35．举例说明支配规则的内容。

36．由最优性原理指出的过程的最优决策序列具有的性质是什么？

答：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。

37．什么样的决策过程构成多阶段决策过程？

答：活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于i 阶段的过程状态，而与i 阶段之前如何到达这种状态的方式无关，这样的过程就构成一个多阶段决策过程。

38．使用动态规划求解问题的前提条件是什么？试举出两个例子，这两个例子都可以看作是多阶段决策问题，但一个例子可以用动态规划来解，而另一个例子不能用动态规划求解。

39．修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？

Procedure ShortestPath(COST, n, A, Max)

integer i , j, k

real COST(n, n), A(n, n), Path(n, n), Max

for i←1 to n do

for j←1 to n do

A(i ,j)←COST(i ,j)

if i≠j and A(i, j)≠Max then Path(i, j )←j else Path(i, j)←0 endif

repeat repeat

for k←1 to n do

for i←1 to n do

for j←1 to n do

if A(i,j)>A(i,k)+A(k,j)

then A(i,j)←A(i,k)+A(k,j) Path(i,j)←Path(i,k) endif

repeat repeat

repeat

for i←1 to n do

for j←1 to n do

print(“the path of i to j is ” i ) k←path(i, j) while k≠0 do print( ,k) k←path(k, j) repeat repeat repeat

end ShortestPath

时间复杂度O(n3)，空间复杂度O(n2) 40.已知图的邻接矩阵

?0?2??9??8103??15027???? 2??0?（1）按照每对结点间的最短路径算法ALL-PATH，求每对结点间的最短路径长度矩阵A4

（2）求路径结点矩阵P。P(i,j)表示从i到j的最短路径的第一步结点。

?0?1P初始如下：??1??1202**3034??*? 4??0?（3）根据P和A4，分别给出结点2到结点4，结点1到结点3的最短路径及长度

解: 计算得:

?0?21

A =??9??8?0?22

A =??5??81039103510351039?1502161502161502911027??0??911? P=??12???0??17??0??912? P=??22???0??17??0??913? P=??22???0??37??0??91? P4=??22???0??3202120232023202123032303410303034??1? 4??0?4??1? 4??0?4??1? 4??0?4??1? 2??0?

?0?23

A =??5??7

?0?24

A =??5??7结点2到结点4的最短路径长为9，最短路径是2→1→4. 结点1到结点3的最短路径长为9，最短路径是1→4→3. 41．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i, 0≤i

解：取(P1,P2,?,Pi,?)=(W1,W2,?,Wi,?)=(20,21,?,2i-1,?)

P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。

42．①递推关系式（6.8）对(P151,图6.16)成立吗？为什么？

②递推关系式（6.8）为什么对于含有负长度环的图不能成立？ 解：①成立，不包含负长度环 ②可以使节点间的长度任意小。

43.设0/1背包问题中(w1,w2,w3,w4)=(10,15,6,9),(p1,p2,p3,p4)=(2,5,8,1),对0≤i≤4，生成每个fi阶跃点的序偶集合Si。 解：S0={(0,0)} S11={(2,10)}

1S={(0,0), (2,10)} S1={(5,15), (7,25)}

22S={(0,0), (2,10), (5,15), (7,25)} S1={(8,6), (10,16) ,(13,21), (15,31)}

33S={(0,0), (8,6), (10,16), (13,21), (15,31)} S1={(1,9), (9,15) ,(11,25),

4(14,30), (16,40)}

4S={(0,0), (8,6), (9,15), (10,16), (13,21), (14,30), (15,31), (16,40)}

44.对于标识符集（a1,a2,a3,a4）=（end, goto, print, stop），已知已知P(1:4)=(1，4，2，1)和Q(0:4)=(4，2，4，1，1)。使用动态规划方法构造一棵最佳二叉排序树（计算出C、W、R阵的结果）。

解: 矩阵W 矩阵C 矩阵R

4721510418137120159 31070221003220703902710202230223 402 1230

最佳二叉排序树为: goto end stop print

45.设n=4, 且( a1,a2,a3,a4)=(do,if,read,while)，已知P(1:4)=(3,3,1,1)和Q(0:4)=(2,3,1,1,1)，使用动态规划方法构造一棵最佳二叉排序树（计算出C、

W、R阵的结果）。 解:

?0?? C=?????80197025123032??2??19??8? W= ???3???0???8312711493116??0??11??5? R=???3???1???1012022302??2?3? ?4?0??

最佳二叉排序树为:

IF DO READ WHILE

46．①证明算法OBST的计算时间是O(n2)。

②在已知根R(i, j)，0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。

解：① 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：

nn?mnn?m

??(R(i?1,j)?R(i,j?1)?1)???(R(i?1,i?m)?R(i,i?m?1)?1)?m?2i?0m?2i?0n?(R(n?m?1,n)?R(0,m?1)?n?m?1)?O(n)

m?22

② Procedure BuildTree(m, n, R, Root)

integer R(n,n), k

TreeNode Root, LR, RR k←R(m,n)

if k≠0 then data(Root)←k,

BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR)

left(Root)←LR, right(Root)←RR

else data(Root)←m, left(Root)←null, right(Root)←null, endif

end BuildTree

时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。

47.设计一个由设备D1,D2,D3组成的三级系统。每台设备的成本分别为30元、15元和20元，可靠性分别为0.9,0.8和0.5，计划建立该系统的投资不得超过105元。假定级有mi台设备Di并联，则该级的可靠性?i(mi)?1?(1?ri)mi。使用

序偶集合的方法求解该问题（要求给出求解过程中产生的所有序偶集合）。 解：s11 ={(0.9,30)} s1={(0.99,60)} 2S={(0.9,30) , (0.99,60)}

s1={(0.72,45),(0.792,75)} s2={(0.864,60)} s3={(0.8928,75)}

2221S={(0.72,45), (0.864,60),(0.8928,75)} s1={(0.36,65),(0.432,80),(0.4464,95)}

32s2={(0.54,85),(0.648,100)} s3={(0.63,105)}

33S={(0.36,65),(0.432,80),(0.54,85),(0.648,100)}

3最优设计有0.648的可靠性,需用资金100元。 m1=1, m2=2, m3=2。

48.对于有a，b两台设备的流水线调度问题，设数组A(n)，B(n)分别存储a，b的任务完成时间。A=(1,5,3,9,7), B=(4,2,8,6,10)，给出这四个作业的调度序列,并给出调度图和调度时间.

答: 对A,B分类后的序列是{a1,b2,a3,b1,a2,b4,a5,b3,a4,b5}

得调度序列为{1,3,5,4,2}

49.修改算法6.1和6.2，使它们只求出问题的一个解而不是问题的全部解 算法6.1

procedure BACKTRACK(n)

integer k,n; local X(1: n) k ← 1

while k>0 do

if还剩有没检验过的X(k)使得

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true then if ( X(1), ? ,X(k) ) 是一条抵达一答案节点的路径 then print ( X(1), ? ,X(k))

return endif

k ←k ＋ 1

else k ←k － 1 endif repeat

end BACKTRACK

算法6.2

procedure RBACKTRACK(k) global n, X(1:n)

for 满足下式的每个X(k)

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true do if ( X(1), ? ,X(k))是一条抵达一答案结点的路径 then print ( X(1), ? ,X(k))

return endif

call RBACKTRACK(k+1) repeat

end RBACKTRACK

50．在关于解空间树结构的术语中，什么是活结点？什么是E-结点？什么叫答案状态？什么是死结点？

51．什么是状态空间树？回溯法求解问题的过程中，状态空间树所有结点没有完全遍历到，但为什么能够得到所有的解？

integer k,n; local X(1: n) k ← 1

while k>0 do

if还剩有没检验过的X(k)使得

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true then if ( X(1), ? ,X(k) ) 是一条抵达一答案节点的路径 then print ( X(1), ? ,X(k))

return endif

k ←k ＋ 1

else k ←k － 1 endif repeat

end BACKTRACK

算法6.2

procedure RBACKTRACK(k) global n, X(1:n)

for 满足下式的每个X(k)

X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true do if ( X(1), ? ,X(k))是一条抵达一答案结点的路径 then print ( X(1), ? ,X(k))

return endif

call RBACKTRACK(k+1) repeat

end RBACKTRACK

50．在关于解空间树结构的术语中，什么是活结点？什么是E-结点？什么叫答案状态？什么是死结点？

51．什么是状态空间树？回溯法求解问题的过程中，状态空间树所有结点没有完全遍历到，但为什么能够得到所有的解？

本文来源：https://www.bwwdw.com/article/46fv.html