《中国科学院大学历年计算机算法作业和历年习题.pdf》由会员分享，可在线阅读，更多相关《中国科学院大学历年计算机算法作业和历年习题.pdf（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、中国科学院大学历年习题习题一复杂性分析初步1.试确定下述程序的执行步数，该函数实现一个m Xn矩阵与一个nX p矩阵之间的乘法：矩阵乘法运算templatevoid Mult(T*a,T*b,int m,int n,int p)/mXn矩阵a 与nX p矩阵b 相成得到m Xp矩阵cfbr(int i=0;im;i+)for(intj=O;jp;j+)T sum=0;fbr(int k=0;kn;k+)Sum+=aik*bkj;Cij=sum;)语 句s/e频率总步数templatevoid Mult(T*a,T*b,int m,int n,int p)000for(int i=0;im;i+
2、)1m+1m+1for(intj=0;jp;j+)1m*(p+l)m*p+mT sum=0;1m*pm*pfbr(int k=0;kn;k+)1m*p*(n+l)m*p*n4-m*pSum+=aik*bkj;1m*p*nm*p*nCij=sum;1m*pm*p总 计2*m*p*n+4*m*p+2*m+l其 中 s/e 表示每次执行该语句所要执行的程序步数。频率是指该语句总的执行次数。2.函数MinMax用来查找数组a0:n-l中的最大元素和最小元素，以下给出两个程序。令 n 为实例特征。试问：在各个程序中，a 中元素之间的比较次数在最坏情况下各是多少？_ _ _ _ _ _ _ _ _ _ _
3、 _ _ _ 找最大最小元素方法一templatebool MinMax(T a,int n,int&Min,int&Max)寻找a0:n-l中的最小元素与最大元素如果数组中的元素数目小于1,则还回falseifnl)return false;Min=Max=0;初始化fbr(int i=l;iai)Min=i;if(aMaxai)Max=i;return true;最好，最坏，平均比较次数都是2*(n-1)找最大最小元素方法二templatebool MinMax(T a,int n,int&Min,int&Max)寻找a0:n-l中的最小元素与最大元素如果数组中的元素数目小于1,则还回fa
4、lseif(nl)return false;Min=Max=0;初始化for(int i=l;iai)Min=i;else if(aMax 85.下面那些规则是正确的？为什么？0-/()=O(F(n),g()=O(G(n)=f(n)/g(n)=O(F(n)/G()；错2)./(n)=O(F(n),g(n)=O(G(n)=/(n)/(n)=Q(F(n)/G(n)；错3)./()=O(F(),g()=O(G()=/()/g()=(F()/G()；错4)./()=QCF(),g()=Q(G()nf()/g()=Q(F()/G()；错5).f()=Q(F(),g()=Q(G()n f()/g()=O(
5、F()/G(”)错6).f(n)=0(F(n),(n)=0(G(n)=/()/g(n)=0(F(n)/G(n)对6.按照渐进阶从低到高的顺序排列以下表达式：4n2,logn,3,20/?,n2 3,n!顺序：lo g n n2 3 20n 4 2 3 nl7.1)假设某算法在输入规模是时为T()=3*2 .在某台计算机上实现并完成该算法的时间是，秒.现有另一台计算机，其运行速度为第一台的6 4 倍,那么，在这台计算机上用同一算法在f秒内能解决规模为多大的问题？关系式为时间复杂度(计算步数)*运行速度(时间/每步)=运行所需时间，即规模时间复杂度(步数)原运行速度(时间/每步)总时间n丁()=3
6、*2tT(n)*t0=t解：设在新机器上f秒内能解决规模为加的问题，时间复杂度变为T(=3*2%由于新机器运行速度提高64倍，则运行速度变为羯=2，由关系式T()*%=f,T(m)*=f，得解得m =n+62)若上述算法改进后，新算法的计算复杂度为T()=2,则在新机器上用，秒时间能解决输入规模为多大的问题？设在新机器上用f秒时间能解决输入规模为N的问题，则由于新复杂度T新(N)=M,新机器的运行速度为*代入关系式4()*乐=，得N2*-=t=3*2n*ta64 0，解得3)若进一步改进算法，最新的算法的时间复杂度为7()=8,其余条件不变，在新机器上运行，在f秒内能够解决输入规模为多大的问题
7、？设可解决的最大时间复杂度为7mX，则T*红=/=3*2乜m d x 才 4 u64可解决的最大时间复杂度为111a x =192*2”,(n为原始的输入规模)。因为T()=8 M a x，且T()为常数不随输入规模n变化，所以任意规模的n都可在t秒内解决。8.F i bo na c c i数有递推关系：1,二 0尸()=1试求出F()的表达式。解：方法一：当 1时，由递推公式()=(1)+尸(-2)得特征方程为x2=x+1解得1 +75 1-75X.=-,x2=-2 2 2则可设F(n)=+c2 K由 F(2)=2,%3)=3,解得2-v 51-752也故尸()=1 +Vs|+|zl-V5,
8、+|丁)一丁)，当 =0,1时，带入验证亦成立。故尸()=1 方法二：也可直接推导F(n)=F(w-l)+F(n-2)可得氏一。4一1 二例 4-1 可得a土耳a，B-2，设bn=%一。%.1，则2为等比数列，先求出勿，然后代入即可求得许。第二章部分习题参考答案1.证明下列结论：1）在一个无向图中，如果每个顶点的度大于等于2,则该该图一定含有圈；2）在一个有向图D中，如果每个顶点的出度都大于等于1,则该图一定含有一个有向圈。1）证明：设无向图最长的迹尸=匕匕丫上,每个顶点度大于等于2,故存在与匕相异的点V，与匕相邻，若W P,则得到比P更长的迹，与 P的取法矛盾。因此，V,e P,是闭迹，从而
9、存在圈匕匕V%.证明*:设在无向图G中，有n 个顶点，m条边。由题意知，m=（2 n）/2=n,而一个含有n 个顶点的树有I 条边。因m=n n T,故该图一定含有圈。（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。）2）证明：设有向图最长的有向迹尸=%匕%,每个顶点出度大于等于1,故存在s为V*的出度连接点，使得K V 成 为 一条有向边，若V Y P,则得到比P更长的有向迹，与P矛盾，因此必有KkP,从而该图一定含有有向圈。2.设D 是至少有三个顶点的连通有向图。如果D中包含有向的Eul er 环游
10、（即是通过D中每条有向边恰好一次的闭迹），则 D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D 一定包含有向的Eul er 环游。这两个结论是正确的吗？请说明理由。如果G 是至少有三个顶点的无向图，则G包含Eul er 环游的条件是什么？证明：1）若图D中包含有向Eul er 环游，下证明每个顶点的入度和出度相等。如果该有向图含有Eul er 环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。2）若图D中每个顶点的入度和出度相等，则该图D包含Eul e
11、r 环游。证明如下。对顶点个数进行归纳。当顶点数|v(D)|=2 时，因为每个点的入度和出度相等，易得构成有向Eul er环游。假设顶点数|v(D)|=k 时结论成立，则当顶点数|v(D)|=k+1 时，任 取 v C v(D)及 S=以 v为终点的边,K=以 v为始点的边,因 为 v的入度和出度相等，故 S和 K中边数相等。记 6=口.对G做如下操作：任 取 S和 K中各一条边q、e2，设 在 D中6 =印，e?=丫 为，则 对 G和 S做 如 下 操 作G =G +V iv2,S=S-e2,重复此步骤直到S为空。这个过程最终得到的G有 k个顶点，且每个顶点的度与在G中完全一样。由归纳假设，
12、G中存在有向Eul er 环游，设 为 C。在 G中从任一点出发沿C的对应边前行，每当遇到上述添加边v l v 2 时，都用对应的两条边el,e2 代替，这样可以获得有向Eul er环游。3)G是至少有三个顶点的无向图，则 G包 含 Eul er 环游等价于G中无奇度顶点。(即任意顶点的度为偶数)。3.设G是具有n个顶点和m 条边的无向图，如果G是连通的，而且满足m =n-1,证 明 G是树。证明：思路一：只需证明G中无圈。若G中有圈，则删去圈上任条边G仍连通。而每个连通图边数e=n(顶点数)-1,但删去一条边后G中只有n-2 条边，此时不连通，从而矛盾，故G中无圈，所以G为树。思路二：当 =
13、2时，根=2-1 =1,两个顶点一条边且连通无环路，显然是树。设当”=女一1 伙e N 2 2)时，命题成立，贝 IJ当=女时，因为G连通且无环路，所以至少存在一个顶点匕，他的度数为1,设该顶点所关联的边为修=(匕,匕)那么去掉顶点匕和/,便得到了一个有k-1 个顶点的连通无向无环路的子图G ,且 G 的边数机=团-1,顶点数 由于m=n-l,所以m=m-1 =(n -1)-1 =n -1,由归纳假设知，G是树。由于G相当于在G 中为丫2添加了一个子节点，所 以G也是树。由(1),(2)原命题得证。4.假 设 用 个-X-的数组来描述一个有向图的九x 九邻接矩阵，完成下面工作：1)编写个函数以
14、确定顶点的出度，函数的复杂性应为2)编写一个函数以确定图中边的数目，函数的复杂性应为0(r)；3)编写一个函数删除边亿力，并确定代码的复杂性。解答：(1)邻接矩阵表示为x“，待确定的顶点为第m个 顶 点 匕 i n t C o u n t V b u t(i n t *a,i n t n,i n t m)i n t o u t =0;f b r(i n t i=0;i n;i-H-)i f(a m-l i =l)o u t ;r e t u r n o u t;(2)确定图中边的数目的函数如下：i n t E d ge N u m b e r(i n t*a,i n t n)i n t n u
15、 m =0;f b r(i n t i=0;i n;i-H-)f b r(i n t j=O;j B-E|O C A JB-A-C|O/C-B-D-E|O 3 C|OE-A-C-F-G|OF-E-G|OG-E-F|O一个无向图G解：初 始 化 数 组 DFN:=O,n um=l；A 为树的根节点，对 A 计算DFN L(A,n ull),DFN(A)：=n um=l;L(A)：=n um=l;n um:=1+1=2。从邻接链表查到A 的邻接点B,因为DFN(B尸0,对 B 计算DFN L(B,A)DFN(B)：=n um=2;L(B)：=n um=2;n um：=2+1=3。查邻接链表得到B
16、的邻接点A,因为DFN(A)=1 M,但 A=A,即是B 的父节点，无操作。接着查找邻接链表得到B 的邻接点C,因为 DF N =0,对 C 计算 DFN L(C,B)DFN(C)：=n um=3;L(C)：=n um=3;n um:=3+l=4。查找C 的邻接点B,因为DFN(B尸I M,但 8=8,即是C 的父节点，无操作。接着查找邻接链表得到C 的邻接点D,因为 DFN(D)=0,对 D 计算 DFNL(D,C),DFN(D)：=n um=4;L(D)：=n um=4;n um:=4+l=50查找得D 邻接点C,而 DFN(C)=3=0,但 C=C,为 D 的父节点，L(D)保持不变。D
17、 的邻接链表结束，DFNL(D,C)的计算结束。返回到D 的父节点C,查找邻接链表得到C 的邻接点E,因为DFN(E尸0,对 E 计算DFN L(E,C),DFN(E)：=n um=5;L(E)：=n um=5;n um:5+l=6;查找得 E 邻接点 A,因 DFN(A)=1 W O,又 AW C,变换 L(E)=m in(L(E),DFN(A)=K查找得E 邻接点C,因 DFN(C)=3 W 0,但 C=C,无操作。查找得E 邻接点F,因 DFN(F尸0,对 F 计算 DFNL(F,E),DFN(F)：=n um=6;L(F)：=n um=6;n um:=6+l=7;查找得F 邻接点E,因
18、 DFN(E)=5 W 0,但=,无操作。查找得F 邻接点G,因 DFN(G)=0,对 G 计算 DFNL(GF),DFN(G)：=n um=7;L(G)：=n um=7;n um=7+l=8；查找 G 邻接点 E,因 DFN(E)=5#0,又 E#F,L 初 in(L(G),DFN(E)=5查找得G 邻接点F,因 DFN(F)=6/0,但 F=F,无操作。G 的邻接链表结束，DFNL(G,F)的计算结束。L(F)：=min(L(F),L(G)=min(6,5)=5F的邻接链表结束,DFNL(F,E)的计算结束。L(E):=in in(L(E),L(F)=m in(1,5)=1E 邻接链表结束
19、，DFN L(E,C)计算结束。L(C):=m in(L(C),L(E)=m in(3,l)=lC 的邻接链表结束，DFN L(C,B)计算结束。L(B):=m in(L(B),L(C)=m in(2,1 )=1查找B 的邻接链表结束，DFN L(B,A)计算结束。L(A):=m in(L(A),L(B)=l查找得 A 的邻接点点 因 DFN(得=0,又 EW n ull,则 L(A)=m in(L(A),DFN(E)=l查找A 的邻接链表结束，DFN L(A,n ull)计算结束。最终结果为：深索数D F N,与最低深索数L如下DFN(A)=L DFN(B)=2,DFN(0=3,DFN(D)
20、=4,DFN(E)=5,DFN (F)=6,DFN(G)=7L(A)=1;L(B)=1;L(C)=1;L(D)=4;L(E)=1;L(F尸5;L(G)=5.序节点DFNL栈顶一栈底2-连通割点1A1(1,0,0,0,0,0,0)(A,B)2B2(1,2,0,0,0,0,0)(B,C),(A,B)3C3(1,2,3,0,0,0,0)(C,D),(B,C),(A,B)4D4(1,2,3,4,0,0,0)(B,C),(A,B)(C,D);c5E5(1,1,1,4,1,0,0)(E,F),(E,A),(B,C),(A,B)6F6(1,1,1,4,1,6,0)(F,G),(E,F),(E.A),(B,C
21、),(A,B)7G7(1,1,1,4,1,5,5)(E,A),(B,C),(A.B)(G,E),(F,G),(E,F)E8(1,1,1,4,1,5,5)(E,A),(B,C),(A,B)附课本讲义程序2-3-1对图2-3-5的执行过程开始 DFNL(A,*)DFN(A):=1;L(A):=1;num:=2;V DFN(B)=O,A DFNL(B,A)DFN(B):=2;L(B):=2;num:=3;DFN(A)=lwO,但 A=A,不做任何事情V DFN(C)=O,A DFNL(C,B)DFN(C):=3;L(C):=3;num:=4;DFN(B)=2M,但 8=8,不做任何事情V DFN(D
22、)=O,DFNL(D,C)DFN(D):=4;L(D):=4 DFN(C);num:=5;DFN(0=3M,但 C=C,不做任何事情V DFN(E)=O,I.DFNL(E,C)DFN(E):=5;L(E):=5 DFN(C);num:=6;弹 出（C,E）边DFN(C)=3M,但=DFN(G);num:=9;DFN(G)=7#0,但 G=G,/DFN=0,J DFNL(I,G)DFN(I):=9;L(I):=9;num:=10;V DFN(F)=6wO,FwG L(I):=min9,6=6;,/DFN(G)=7wO,但 G=G,DFN(J)=0,DFNL(J,I)DFN(J):=10;L(J)
23、:=10;num:=ll;,/DFN(F)=6wO,Fwl,/.L(J):=min10,6=6;,/DFN(G尸J L(J):=min6,7=6;DFN(I)=9wO,但 1=1,L(I):=min 6,6=6;L(G):=min7,6=6 DFN(F)(I,F),(G,I),(F,G)边L(F):=minl,6=l;L(C):=min3,l=1;L(B):=min2,l=l DFN(A)弹出(J,G),(J,F),(I,J),弹出(F,A),(C,F),(B,C),(A,B)边7 对图的另一种检索方法是D-Search。该方法与BFS的不同之处在于将队列换成栈，即下一个要检测的结点是最新加到
24、未检测结点表的那个结点。1)写一个D-Search算法；2)证明由结点v 开始的D-Search能够访问v 可到达的所有结点；3)你的算法的时、空复杂度是什么？解：1)同第5 题，proc DBFS(v)宽度优先搜索G,从顶点v 开始执行，数组visited标示各顶点被访问的序数；数组s 将用来标示各顶点是否曾被放进待检查队 列，是则过标记为1,否则标记为0;计数器count计数到目前为止已经被访问的顶点个数，其初始化为在v 之前一经被访问的顶点个数PushS(v,S);/将 S 初始化为只含有一个元素v 的栈while S 非空 dou:=PullHcad(S);count:=count+l
25、;visitedu:=count;fo r邻接于u 的所有顶点w doif sw=0 thenPushS(w,S);将w 压入栈中sw:=l;end ifend forend while)endDBFS图的D一搜索算法伪代码：proc DBFT(G,v)/count、s 同 DBFS中的说明，branch是统计图G 的连通分支数count:=0;branch:=0;fbr i to n dosi:=0;将所有的顶点标记为未被访问end fbrfbr i to v doif si=0 thenDBFS(i);branch:=branch+l;e n d if e n d f o r e n d
26、DBFT2)证明：除结点v 外，只有当结点w 满 足 s w=O时才被压入栈中，因此每个结点至多有一次被压入栈中，搜索不会出现重叠和死循环现象，对于每一个v可到达的节点，要么直接被访问，要么被压入栈中，只有栈内节点全部弹出被访问后，搜索才会结束，所以由结点v开始的D-S ea rc h能够访问v 可到达的所有结点。3)：除结点v外，只有当结点w满足sw =O时才被压入栈中，因此每个结点至多有一次被压入栈中。需要的栈空间至多是v-l；v isit ed 数组变量所需要的空间为v；其余变量所用的空间为0(1),所以s(v,尸 (v)。如果使用邻接链表，fo r循环要做d(u)次，而 w hil e
27、循环需要做v 次，又 v isit ed、s和 c o un t的赋值都需要v 次操作，因而t(v,尸 (v+)。如果采用邻接矩阵，则 w hil e循环总共需要做v 2 次操作，v isit ed s和 c o un t 的赋值都需要v 次操作，因而t(v ,)=0 (v 2)08.考虑下面这棵假想的对策树：解：1)使用最大最小方法(2-4-2)式获取各结点的值maxminmaxminmax2)2）弈者A为获胜应该什么棋着?X i.i.iX.1.1.13）列出算法VEB计算这棵对策树结点的值时各结点被计算的顺序14)对树中每个结点X,用(2-4-3)式计算V(X)；5)在取X=根，1=10,
28、L B=-8.D=8的情况下，用算法AB计算此树的根的值期间，这棵树的那些结点没有计算？520第三章分治算法习题1、编写程序实现归并算法和快速排序算法参见后附程序2、用长为 100,200、300、400、500、600、700、800、900、1000 的 10 个数组的排列来统计这两种算法的时间复杂性。有些同学用的微秒us用 s 可能需要把上面的长度改为10000,100000,都可以大部分的结果是快速排序算法要比归并算法快一些。3、讨论归并排序算法的空间复杂性。解析：归并排序由分解与合并两部分组成，如果用S()表示归并排序所用的空间。则由MergeSort(low,mid)/将第一子数组
29、排序 S(nl 2)MergeSort(mid+l,high)将第二子数组排序 5(/2)Merge(low,mid,high)归并两个已经排序的子数组。()=2n则S(n)=m a x S(n/2),0()S()S(/2)+O()递归推导得S(n)S g)+O()+0()+.+6(-)+。S(1)+O(2 n)=O(n)又由存储数组长度 为 ，则 有S()2 O()因此，空间复杂度为0(“)。4、说明算法PartSelect的时间复杂性为。()证明：提示：假定数组中的元素各不相同，且第一次划分时划分元素u是第i小元素的概率为1/。因为Partition中的case语句所要求的时间都是。()，
30、所以，存在常数c,使得算法 PartSelect的平均时间复杂度。：()可以表示为0()W c +匕Z(一i)+Z C：(1)i k ki n令 R()=m a x(C；(),取 C 2 /?(1),试证明 R()4 c。k证明：令。；()表 示n个 元 素 的 数 组A中 寻 找 第k小元素的平均时间复杂度，因Pa r t i t i on(0,n -1)的时间复杂度是。(“)，故存在常数c,使得算法Pa r t Se l e ct的平均时间复杂度C可以表示为C：(/)C +工(Z(-0+EC：(i T)i k ki n令/?()=m a x(C：(),且不妨设等式在k=儿时成立，则/?()
31、满足kR()W c +工(Z W(一 i)+Z C G -l)n l i k ki n以下用第二数学归纳法证明/?()R(l),当”=1时，取c2 c/4,则R W 4 c当=2 时，R(2)W 2 c+；R(l)W 2 c+g 4 c=4 c 成立。对于一般的n,设对所有小于n的自然数4 c成立，则R()c n+-(R(n-l)+-+R(n-k+1)+(R伙“)+R伙“+1)+R(-1)n4cc n-(-1)H-F(-+1)+(kn H-F(n -1)nW c +竺代 1)(2 勺)+(：“)&+(T)n 2 2 c n-(k：(n+l)k,-鼠；吗n 2/3/-4/?+lc n+c-n c
32、 n+c(3 n-3)4c n得证。证明：(1)当r =7时，假设数组A中元素互不相同。由于每个具有7个元素的数组的中间值U是该数组中的第4小元素，因此数组中至少有4个元素不大于U,1/7 个中间值中至少有w/7/2个不大于这些中间值的中间值v。因此，在数组A中至少有4*/7/222 山 7个元素不大于v。换句话说，A中至多有5 1 2-/7=-2(/7-e/7)y z?+,(0 e 6)5 1 2个元素大于v。同理，至多有一 +一个元素小于v。这样，以v为划分元素，产生的新数7 75 1 2 5 1 2 1 1组至多有士+上个元素。当豆24时，-n+/i o7 7 7 7 1 4另一方面，在
33、整个执行过程中，递归调用Se l e ct函数一次，涉及规模为”/7,而下一次循环Lo o p涉及的数组规模为U”。程序中其他执行步的时间复杂度至多是n的倍数5,用1 4T()表示算法在数组长度为n的时间复杂度，则当 2 24时，有递归关系T(n)T(n)+T(n)+cn用数学归纳法可以证明，7()1 4 cn o所以时间复杂度是。()。2 2 5(2)当=3时，使用上述方法进行分析，可知在进行划分后数组A中有至多*+-3 3 6个元素。而递归关系为7()7己)+7(9)+。若通过归纳法证明出有7()必1的3 6形式，用数学归纳法可以证明，T(n)2 8cn o所以时间复杂度是。()。归并排序
34、的C 语言描述#i n cl u de t e m p l a t e voi d M e r g e Sor t(T a ,i n t l e f t,i n t r i g h t);t e m p l a t e voi d M e r g e(T c,T d,i n t l,i n t m,i n t r);t e m p l a t e voi d Cop y(T a ,T b ,i n t l,i n t r);voi d m a i n()i n t con s t n(5);i n t a n ;c o u t nIn p u t ,*n,*n u m b e r s p l
35、e a s e:；f or(i n t i=0;i n;i+)ci n a i ;/f b r(i n t j=O;j n;j+)/b U =a j ;M e r g e Sor t(a,0,n-1);c o u t nT h e s or t e d a r r a y i sne n dl;f or(i=0;i n;i+)cou t a i ;coutendl;templatevoid MergeSort(T a,int left,int right)/if(leftright)(int i=(left+right)/2;T*b=new T;MergeSort(a,left,i)；Merg
36、eSort(a,i+1,right);Merge(a,b,left,i,right);Copy(a,b,left,right);templatevoid Mergc(T c,T d,int l,int m,int r)int i=l;int j=m+l;int k=l;while(i=m)&(j=r)if(cim)(M int q=j;q=r;q+)dk+=cq;)elsefbr(int q=i;q=m;q+)dk-H-=cq;)templatevoid Copy(T a,T b,int l,int r)for(int i=l;i=r;i+)ai=bi；快速排序的C+语言描述#includet
37、emplatevoid QuickSort(T a,int p,int r);tcmplateint Partition(T a,int p,int r);void main()int const n(5);int an;coutInput,n,numbers please:11;for(int i=0;in;i-H-)cinai;QuickSort(a,0,n-1);coutThe sorted array isnendl;fbr(i=O;in;i-H-)coutain H;coutendl;templatevoid QuickSort(T a,int p,int r)if(P r)int
38、q=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1 ,r);)templateint Partition(T a,int p,int r)int i=pj=r+l;T x=ap;while(true)while(a-H-ix);if(i=j)break;Swap(ai,a|j);)ap=aj；aj=x;return j;templateinline void Swap(T&s,T&t)T temp=s;s=t;t=tcmp;第四章作业部分参考答案1.设有个顾客同时等待一项服务。顾客i需要的服务时间为小应该如何安排个顾客的服务次序才能使总的
39、等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由(证明)。策略：对4 W 进行排序，乙斗，然后按照递增顺序依次服务3 2,即可。解 析：设 得 到 服 务 的 顾 客 的 顺 序 为/,1，则 总 等 待 时 间 为T=(-1)+(-2*+2tM+5T，则在总等待时间T中tj i的权重最大，J的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证明：设0 W%T.由于7=(一 1)%+(-2)也 +2%_2+*,T=(n-l)r.+(n-2儿+(-z)?.+(/?-j)q+11+2*+%,f =(n-1)+(n-2)%+(”一，)+(-j)/,+2f.
40、_2+f*,则有同理可证其它次序，都 可 以 由 经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而，也）为最优策略。2.字符。h出现的频率分布恰好是前8个Fibonacci数，它们的Huffman编码是什么？将结果推广到个字符的频率分布恰好是前个Fibonacci数的情形。Fibonacci数的定义为：尸。=L瓦=L工=死-2+尸”-1 /1解：前 8 个数为 a,b,c,d,e,f,g,h1,1,2,3,5,8,13,21Huffman哈夫曼编码树为：所以a的编码为：1111111b的编码为：1111110c的编码为：111110d的编码为：11110e 的编码为：mof 的编码为
41、：110g的编码为：10h的编码为：0推广到n个字符：第 1个字符：n-1个 1,1_T 4n-l第 2个字符：n-2 个 1,1个 0,H-10n 2第 3 个字符：n-3 个 1,1个 0,H-10n-3第 n-1个字符：1个 1 ,1个 0,10第 n个字符：1个 0 ,03.设p“P 2,p”是准备存放到长为L的磁带上的n 个程序，程序P：需要的带长为为。设之 乙，要求选取一个能放在带上的程序的最大子集合（即其中/=1含有最多个数的程序）。构造。的一种贪心策略是按q的非降次序将程序计入集合。1）证明这一策略总能找到最大子集0,使得2）设。是使用上述贪心算法得到的子集合，磁带的利用率可以
42、小到何种程度？3）试说明1）中提到的设计策略不一定得 到 使 取 最 大 值 的 子 集 合。Pi Q1）证明：不妨设q 4 V。，若该贪心策略构造的子集合。为 4，。2,，则S 满足W L、+4+1 L o/=!/=1要证明能找到最大子集，只需说明S 为可包含的最多程序段数即可。即证不存在多于s 个的程序集合0 =f l.,as,-（,（k s）,使得W L oPi Q反证法，假设存在多于S个的程序集0 =4,%,满足2因为q W s且为整数,则其前S+1项满足4 +。2+4 +见+1L。这与贪心策略构造的子集和。中S满足的f a,+4+1 L矛盾。故假设不成立，得证。i=l2)磁 带 的
43、利 用 率 为工 aJ L;(甚 至 最 小 可 为0,此 时 任 意4 L或 者、,)Pi Q Pi Q3)按 照1)的 策 略 可 以 使 磁 带 上 的 程 序 数 量 最 多，但程序的总长度不一定是最大的，假设也为Q的 最 大 子 集，但 是 若 用 代 替 火,仍 满 足1-1X4+,+1 L ,则%,电，,%-1，%+为 总 长 度 更 优 子 集。k=l4.同学们的儿种不同答案构造哈夫曼树思想，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点(树根)。答
44、案1)伪代码：typedef struct(unsigned int weight;unsigned int parent,Ichi Id,rchild;JHTNode,*HuffmanTree;typedef char*HuffmanCode;proc HuffmanCoding(HufTmanTree&HT,HuffmanCode&HC,int*w,int n)if n=1 then returnHuflmanTree p;integer si,s2,i,m,start,c,char*cd;m:=2*n-1;HT0.weight:=1000000;p:=HT+1;fbr i to n do
45、(*p).wcight:=*w;(*p).parent:=(*p).lchild:=(*p).rchild:=0;+p；-H-W；end fbrfor i to m do(*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0；+P；end forfbr i from n+l to m doSelect(HT,i-1,si,s2);HTsl.parent:=i;HTs2.parent:=i;HTi.lchild:=si;HTi.rchild:=s2;HTi.weight:=HTsI.weight+HTs2.weight;end forcdn-l=,0,
46、;编码结束符for i to n dostart:=n-l;编码结束符位置f:=i;c:=i;for f from HTf.parent to f=0 doifHTf.lchild=ccd-start:=O;elsecd-start:=*r；end elseend ifend fbrend fbrend HuffmanCoding源代码：#include#include#include/include using namespace std;#dcfinc infinite 50000/定义Huffman树和Huffman编码的存储表示typedef structunsigned int we
47、ight;字符的频数unsigned int parent,Ichild,rchild;双亲结点，左孩子，右孩子HTNode,*HuffmanTree;typedef char*HuffmanCodc;void Select(HuffinanTree HT,int n,int&sl,int&s2);void HufFmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n);void main()(int i,n,*w;cout enter the size of the code:cin n;cout endl;w=(int*)malloc(n+
48、1)*sizeofifint);cout enter the weight of the code:Mendl;for(i=l;i=n;i+)/逐个输入每个字符的出现的频数，并用空格隔开cinwi;HuffmanTrcc HT;HuflmanCode HC;HufTinanCoding(HT,HC,w+1,n);cout”the huffinancode is:H end I;fbr(i=l;i=n;i+)coutw i,:；coutH C iH”；coutendl;system(pause1);在HuffmanTree中HT1可选择parent为且weight最小的两个结点，其序号分别为s
49、i和s2void Select(HufImanTree HT,int n,int&sl,int&s2)(int i;si=s2=0;fbr(i=l;i HTi.weight)s2=i;elseif(HTi.parent=0&HTsl.weight HTi.wciglit)si=i;/构造Huffman树 H T,并求出n 个字符的Huffman编码HCvoid HuffinanCoding(HuffmanTree&HT,HuffinanCode&HC,int*w,int n)if(n=1)return;HufTinanTree p;int si,s2,i,m,start,c,f;char*cd
50、;m=2*n-1;HT=(HuffinanTree)malloc(m+l)*sizeof(HTNode);HT0.weight=infinite;/将号单元置一个较大的数fbr(p=HT+l,i=l;i=n;+i,+p,+w)(*p).weight=*w;将n 个字符的频数送到HT.weightl.n(*p).parent=(*p).lchild=(*p).rchild=0;双亲孩子初始化为)fbr(;i=m;+i,+p)(*p).weight=(*p).parent=(*p).Ichi Id=(*p).rchild=0;/将 HufTmanTree结点权值HT.weightn+lm+1(频数