中科院计算机算法设计与分析各章作业+历年习题

1中国科学院大学历年习题习题一复杂性分析初步1.试确定下述程序的执行步数，该函数实现一个m×n矩阵与一个n×p矩阵之间的乘法：矩阵乘法运算templateclassTvoidMult(T**a,T**b,intm,intn,intp){//m×n矩阵a与n×p矩阵b相成得到m×p矩阵cfor(inti=0;im;i++)for(intj=0;jp;j++){Tsum=0;for(intk=0;kn;k++)Sum+=a[i][k]*b[k][j];C[i][j]=sum;}}其中s/e表示每次执行该语句所要执行的程序步数。频率是指该语句总的执行次数。2．函数MinMax用来查找数组a[0:n-1]中的最大元素和最小元素，以下给出两个程序。令n为实例特征。试问：在各个程序中，a中元素之间的比较次数语句s/e频率总步数templateclassTvoidMult(T**a,T**b,intm,intn,intp)000{for(inti=0;im;i++)1m+1m+1for(intj=0;jp;j++){1m*(p+1)m*p+mTsum=0;1m*pm*pfor(intk=0;kn;k++)1m*p*(n+1)m*p*n+m*pSum+=a[i][k]*b[k][j];1m*p*nm*p*nC[i][j]=sum;1m*pm*p}}总计2*m*p*n+4*m*p+2*m+12在最坏情况下各是多少？找最大最小元素方法一templateclassTboolMinMax(Ta[],intn,int&Min,int&Max){//寻找a[0:n-1]中的最小元素与最大元素//如果数组中的元素数目小于1，则还回falseif(n1)returnfalse;Min=Max=0;//初始化for(inti=1;in;i++){if(a[Min]a[i])Min=i;if(a[Max]a[i])Max=i;}returntrue;}最好，最坏，平均比较次数都是2*（n-1）找最大最小元素方法二templateclassTboolMinMax(Ta[],intn,int&Min,int&Max){//寻找a[0:n-1]中的最小元素与最大元素//如果数组中的元素数目小于1，则还回falseif(n1)returnfalse;Min=Max=0;//初始化for(inti=1;in;i++){if(a[Min]a[i])Min=i;elseif(a[Max]a[i])Max=i;}returntrue;}最坏2*（n-1），最好n-1,平均2)1(3n3.证明以下不等式不成立：1).);(9102nOn2).)(log22nnn；34．证明：当且仅当0)(/)(limngnfn时，))(()(ngonf。5.下面那些规则是正确的？为什么？1).))(/)(()(/)())(()()),(()(nGnFOngnfnGOngnFOnf；错2).))(/)(()(/)())(()()),(()(nGnFngnfnGOngnFOnf；错3).))(/)(()(/)())(()()),(()(nGnFngnfnGOngnFOnf；错4).))(/)(()(/)())(()()),(()(nGnFngnfnGngnFnf；错5).))(/)(()(/)())(()()),(()(nGnFngnfnGngnFnf。错6).))(/)(()(/)())(()()),(()(nGnFngnfnGngnFnf对6.按照渐进阶从低到高的顺序排列以下表达式:!,,20,3,log,43/22nnnnnn顺序：!3420log23/2nnnnnn7.1)假设某算法在输入规模是n时为nnT2*3)(.在某台计算机上实现并完成该算法的时间是t秒.现有另一台计算机,其运行速度为第一台的64倍,那么,在这台计算机上用同一算法在t秒内能解决规模为多大的问题?关系式为时间复杂度（计算步数）*运行速度(时间/每步)=运行所需时间，即ttnT0*)(解：设在新机器上t秒内能解决规模为m的问题，时间复杂度变为mmT2*3)(，由于新机器运行速度提高64倍，则运行速度变为640tt新，由关系式,*)(0ttnTttmT新*)(，得ttn0*2*3，ttm64*2*30解得规模时间复杂度（步数）原运行速度（时间/每步）总时间nnnT2*3)(0tt46nm2)若上述算法改进后，新算法的计算复杂度为2)(nnT,则在新机器上用t秒时间能解决输入规模为多大的问题？设在新机器上用t秒时间能解决输入规模为N的问题，则由于新复杂度2)(NNT新，新机器的运行速度为640tt新，代入关系式ttNT新新*)(，得002*2*364*tttNn，解得nN2383）若进一步改进算法，最新的算法的时间复杂度为8)(nT，其余条件不变，在新机器上运行，在t秒内能够解决输入规模为多大的问题？设可解决的最大时间复杂度为maxT，则00max*2*364*tttTn可解决的最大时间复杂度为nT2*192max，（n为原始的输入规模）。因为max8)(TnT，且)(nT为常数不随输入规模n变化，所以任意规模的n都可在t秒内解决。8.Fibonacci数有递推关系：1),2()1(1,10,1)(nnFnFnnnF试求出)(nF的表达式。解：方法一：当1n时，由递推公式)2()1()(nFnFnF得特征方程为512xx解得2511x，2512x则可设nnxcxcnF2211)(由2)2(F，3)3(F，解得52511c，52512c故])251()251[(51)(11nnnF，当1,0n时，带入验证亦成立。故])251()251[(51)(11nnnF方法二：也可直接推导)2()1()(nFnFnF可得)][211nnnnaaaa可得251,，设1nnnaab，则nb为等比数列，先求出nb，然后代入即可求得na。6第二章部分习题参考答案1.证明下列结论：1）在一个无向图中，如果每个顶点的度大于等于2，则该该图一定含有圈；2）在一个有向图D中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。1）证明：设无向图最长的迹,10kVVVP每个顶点度大于等于2，故存在与1V相异的点'V与0V相邻，若,'PV则得到比P更长的迹，与P的取法矛盾。因此，PV'，是闭迹，从而存在圈.0'10VVVV证明*：设在无向图G中，有n个顶点，m条边。由题意知，m=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m=nn-1，故该图一定含有圈。（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。）2）证明：设有向图最长的有向迹,10kVVVP每个顶点出度大于等于1，故存在'V为kV的出度连接点，使得'VVk成为一条有向边，若,'PV则得到比P更长的有向迹，与P矛盾，因此必有PV'，从而该图一定含有有向圈。2.设D是至少有三个顶点的连通有向图。如果D中包含有向的Euler环游（即是通过D中每条有向边恰好一次的闭迹），则D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D一定包含有向的Euler环游。这两个结论是正确的吗？请说明理由。如果G是至少有三个顶点的无向图，则G包含Euler环游的条件是什么？证明：1）若图D中包含有向Euler环游，下证明每个顶点的入度和出度相等。如果该有向图含有Euler环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。2）若图D中每个顶点的入度和出度相等，则该图D包含Euler环游。证明如下。7对顶点个数进行归纳。当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler环游。假设顶点数|v(D)|=k时结论成立，则当顶点数|v(D)|=k+1时，任取v∈v(D).设S={以v为终点的边}，K={以v为始点的边}，因为v的入度和出度相等，故S和K中边数相等。记G=D-v.对G做如下操作:任取S和K中各一条边21ee、，设在D中vve11，22vve，则对G和S做如下操作21vvGG,}{2eSS，重复此步骤直到S为空。这个过程最终得到的G有k个顶点，且每个顶点的度与在G中完全一样。由归纳假设，G中存在有向Euler环游，设为C。在G中从任一点出发沿C的对应边前行，每当遇到上述添加边v1v2时，都用对应的两条边e1，e2代替，这样可以获得有向Euler环游。3）G是至少有三个顶点的无向图，则G包含Euler环游等价于G中无奇度顶点。（即任意顶点的度为偶数）。3．设G是具有n个顶点和m条边的无向图，如果G是连通的，而且满足m=n-1,证明G是树。证明：思路一：只需证明G中无圈。若G中有圈，则删去圈上任一条边G仍连通。而每个连通图边数e=n(顶点数)–1，但删去一条边后G中只有n-2条边，此时不连通，从而矛盾，故G中无圈，所以G为树。思路二：当2n时，112m，两个顶点一条边且连通无环路，显然是树。设当)2,(1kNkkn时，命题成立，则当kn时，因为G连通且无环路，所以至少存在一个顶点1V，他的度数为1，设该顶点所关联的边为).,(211VVe那么去掉顶点1V和1e，便得到了一个有k-1个顶点的连通无向无环路的子图'G，且'G的边数1'mm，顶点数1'nn。由8于m=n-1,所以11)1(1''nnmm，由归纳假设知，'G是树。由于G相当于在'G中为2V添加了一个子节点，所以G也是树。由（1），（2）原命题得证。4.假设用一个nn的数组来描述一个有向图的nn邻接矩阵，完成下面工作：1）编写一个函数以确定顶点的出度，函数的复杂性应为);(n：2）编写一个函数以确定图中边的数目，函数的复杂性应为);(2n3）编写一个函数删除边),(ji，并确定代码的复杂性。解答：（1）邻接矩阵表示为nna，待确定的顶点为第m个顶点mvintCountVout(int*a,intn,intm){intout=0;for(inti=0;in;i++)if(a[m-1][i]==1)out++;returnout;}（2）确定图中边的数目的函数如下：intEdgeNumber(int*a,intn){intnum=0;for(inti=0;in;i++)for(intj=0;jn;j++)if(a[i][j]==1)num++;returnnum;}（3）删除边（i,j）的函数如下：voiddeleteEdge(int*a，inti,intj){if(a[i-1][j-1]==0)return;a[i-1][j-1]=0;return;9}代码的时间复杂性为Θ(1)5.实现图的D-搜索算法，要求用SPARKS语言写出算法的伪代码，或者用一种计算机高级语言写出程序。解:D搜索算法的基本思想是，用栈代替BFS中的队列，先将起始顶点存入栈中，搜索时，取出栈顶的元素，遍历搜索其相邻接点，若其邻接点还未搜索，则存入栈中并标记，遍历所有邻接点后，取出此时栈顶的元素转入下一轮遍历搜索，直至栈变为空栈。ProcDBFS(v)//从顶点v开始，数组visited标示顶点被访问的顺序；PushS(v,S);//首先访问v,将S初始化为只含有一个元素v的栈count:=count+1;visited[v]:=count;WhileS非空dou:=PullHead