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