数据结构与算法习题讲解(全)

第一章1.5编写一个递归方法，它返回数n的二进制表示中1的个数。利用这样的事实：如果n是奇数，那么它等于n/2的二进制表示中1的个数加1。①intones(intn){if(n2)returnn;returnn%2+ones(n/2);}②#includeiostream.husingnamespacestd;intj=0;count(intn){intk;k=n/2;j++;while(k=1){if(n%2==0)j--;returncount();}}main(){inti,j;cout“Pleaseinputn:”endl;cini;if(i0)i=-i;count(i);cout“所输入整数中的二进制中1的个数是：”jendl;return0;}1.7证明下列公式a.logxx对所有的x0成立①数学归纳法：当0x≤1,命题显然成立：x=1,公式是成立的；当x1时,logx是负数。同理可以很容易推出当1x≤2时命题成立：x=2,公式成立；当x2,logx最大为1。假设命题在px≤2p时成立(p为正整数),这时考虑有2pY≤4p(p≥1)。则logy=1+log(y/2)1+y/2y/2+y/2≤y,由此可推导出公式成立。②二项式法：令x=2x,有log2x2x,即x2x又2x=(1+1)x=C0x+C1x+…+Cxx=1+x+C2x+…+x+1x即2xx,得logxx;命题得证b.log(AB)=BlogA证明：令2X=A,则AB=(2X)B=2XB;则logAB=XB,X=logA;命题得证第二章2.1按增长率排列函数：N,N1/2,N1.5,N2,NlogN,Nlog(logN),Nlog2N,Nlog(N2),2/N,2N,2N/2,37,N2logN,N3。指出哪些函数以相同的增长率增长。答：2/N,37,N1/2,N,Nlog(logN),NlogN,Nlog(N2),Nlog2N,N1.5,N2,N2logN,N3,2N/2,2N.其中，NlogN,Nlog(N2)有相同的增长率。常见的几种计算时间的关系：O(1)O(logN)O(N)O(NlogN)O(N2)O(N3)O(2N)O(N!)O(NN)2.7对于下列六个程序片段中的每一个：给出运行时间分析1)sum=0;2)sum=0;for(i=0;in;i++)for(i=0;in;i++)sum++;for(j=0;jn;j++)O(N)sum++;O(N2)3)sum=0;for(i=0;in;i++)for(j=0;jn*n;j++)sum++;O(N3)4)sum=0;for(i=0;in;i++)for(j=0;ji;j++)sum++;O(N2)5)sum=0;for(i=0;in;i++)for(j=0;ji*i;j++)for(k=0;kj;k++)sum++;O(N5)j可等规模于i2,同样也等规模于N2.k等规模于j,即N2.则该程序段的运行时间复杂度分析为N*N2*N2,即O(N5).6)sum=0;for(i=1;in;i++)for(j=1;ji×i;j++)*if(j%i==0)for(k=0;kj;k++)sum++;O(N4)注：*处的for语句的循环次数为“12+22+32+…+n2”,如上题所述if语句至多要执行N3次,但是实际上只有O(N2)次(因为对每一个i，实际上都严格执行了i次),因此最内的循环只执行了O(N2)次。而每执行一次,将花费O(j2)=O(N2)的时间,总数即为O(N4)。个人理解：if(j%i==0)for(k=0;kj;k++)sum++;这段程序段的循环次数O(N)2.8假设需要生成n个自然数的一个随机置换。例如：{4,3,1,5,2}和{3,1,4,2,5}就是合法的置换，但{5,4,1,2,1}则不是，因为数1出现2次而数3却没有。这种程序常常用于模拟一些算法。我们假设存在一个随机数生成器n，它用方法randInt(i,j)以相同的概率生成i和j之间的一个整数。下面是三个算法：(1).如下填入从a[0]到a[n-1]的数组a:为了填入a[i],生成随机数直到它不同于已经生成的一个a[0],a[1],…,a[i-1]时再将其填入；(2).同算法(1)，但是要使用一个附加的数组，称之为used数组。当一个随机数ran最初被放入数组a的时候，设置used[ran]=ture。就是说，当一个随机数填入a[i]时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样可能用i步来测试；(3).填写该数组，使得a[i]=i+1，然后for(i=1;in;i++)swap(a[i],a[randInt(0,i)]);试问：a.证明这三个算法都生成合法的置换，并且所以的置换都是等可能的；b.对每个算法都给出你能够得出的尽可能不同的期望运行时间分析；c.没个算法的最坏情形的运行时间是什么？答：a.所有的算法都可以生成合法的置换。很明显，前2个算法在测试中可以保证不生成重复的数，并且它们是完全随机的，故它们生成的置换是等可能。第3个算法轮换数组中的元素，这个数组最初是没有重复数的，也不会存在非法置换。前2个算法很明显成立，第3个算法可以用数学归纳法证明，详细证明如下：1.当n=1时，a[0]=1，都是100%，成立；2.当n=2时，for(i=1;in;++i)swap(a[i],a[randInt(0,i)]);第一次循环，当i=1时，即a[0]=1,a[i]=a[1]；3.当n=3时，第二次循环时，当i=2时，此时有两种可能，原序列为0,1;1,0的几率各为50%。randInt(0,2)可能为0,1,2的几率各为1/3。此时,原序列为0,1时,randInt(0,2)为0,那么此序列经过swap(a[2],a[0]),最后序列为2,1,0,此序列的可能性为(1/2)*(1/3)=1/6;同理易得,最后此序列为“210,021,012,201,120,102”的几率各为1/6,而此序列的所有排列可能为=3*2=6,所以，此时成立。4.假设此命题在n=k时成立，那么就是说，ｋ前面序列共有序列k-1种，且所有序列的几率为1/((k-1)*k)。5.当n=k+1时,第k+1次循环时,前面序列正好为n=k时的情况,此时i=k.randInt(0,k)共可能为0~k,k+1种可能。所以以前的每个可能序列在置换后有k+1种可能，而以前共有k种等可能序列，那么最后可能的序列为k*(k+1)种可能，并且，因为原序列为等可能的，每个等可能序列产生的序列都是k+1种，所以最后的序列也是等可能的。而当n=k+1时，应该共有=(k+1)*k种，所以，此命题得证。注：证明时默认地利用了一个命题：当原序列为互不相等的等可能序列时，新加入一个与原来序列任何数值都不相等的数值，无论这个数值放在原序列的哪个位置，都不可能使原不相等的序列相等。例：210,021,012,201,120,102，这时加入一个新的数值3，无论把3插入序列的哪个位置，因为原来序列的排列不相等，所以，他们还是不会相等，这样，才保证了最后k个序列的k+1种可能都不相等，不会重复。b.第一个算法中，决定a[i]中一个之前没有使用过的随机数是否被填入的时间是O(i)。在那些需要测试的随机数中，需要产生期望的随机数的次数为N/(N−i)次。得出结论如下：n个数中有i个可能是重复的。因此，置换成功的概率为(N−i)/N。因此，在独立的测试中，期望数为N/(N−i)。时间复杂度即为：第2个算法为每个随机数保留了因子i，因此，时间度平均减少到了O(NlogN)。第3个算法很明显是线性的，O(N)。c.算法1和算法2的最坏运行时间无法被界定，在一直随机到重复数字的时候可以到达无限大。算法3的运行时间是线性的——它的运行时间并不依赖于随机数的次序。2.12一个算法对于大小为100的输入花费0.5ms，如果运行时间如下：则用1min可以解决多大的问题(设低阶项可以忽略)。a.是线性的；b.为O(NlogN)c.是二次的；d.是三次的(a)12000timesaslargeaproblem,orinputsize1,200,000.N=60*1000*100/0.5=12,000,000=1.2*107(b)inputsizeofapproximately425,000.由NlogN=1.2*107可得(c)120001/2timesaslargeaproblem,orinputsize10,954.由N2=1.2*107可得(d)120001/3timesaslargeaproblem,orinputsize2,289.由N3=1.2*107可得2.18数值分析中一个重要的问题是对某一个任意的函数f找出方程f(x)=0的一个解。如果该函数是连续的，并有两个点low和hign使得f(low)和f(high)符号相反，那么在low与high之间必然存在一个根。并且这个根可以通过二分搜索求得。写一个函数，以f,low和high为参数，并且解出一个零点。floatfind(floatlow,floathigh){mid=(low+high)/2;if(fabs(f(mid))=0.000001)returnmid;elseif(f(mid)*f(low)0)find(low,mid);elsefind(mid,high);}为使程序正常终止，必须设置基准情况。（注意精度防止溢出）一个例子：#includestdio.h#includemath.hfloatf(floata){return5*a+1;}voidfind(float,float);floatstaticc=0;voidmain(){find(-4,5.0);printf(%f\n,c);return0;}voidfind(floatlow,floathigh){floatmid=(low+high)/2;if(fabs(f(mid))=0.0001){c=mid;}else{if(f(mid)*f(low)0)find(low,mid);elsefind(mid,high);}}2.26大小为N的数组A，其主元素是一个出现超过N/2次的元素(从而这样的元素最多有一个)。例如：数组：3,3,4,2,4,4,2,4,4有一个主元素4；而数组3,3,4,2,4,4,2,4没有主元素。如果没有主元素，那么你的程序应该指出来。a.递归如何终止？b.当N是奇数时的情形如何处理？c.该算法的运行时间是多少？d.我们如何避免使用附加数组B？a.如果只有2个或更少的元素，不需要递归。b.一种方法是：标记，如果前N-1个元素已经出现主元素，则最后一个元素不需要考虑。否则，最后一个元素有可能是主元素。因此当N是奇数时，忽略最后一个元素。像之前一样运行算法。如果没有主元素出现，则将第N个元素作为候选值返回。c.运行时间为O(N),并且满足T(N)=T(N/2)+O(N)。d.保存一份数据到数组B。之后，通过复制每一个Bi到数组A即可避免递归。区别在于原递归策略将要用到O(logN)个数组，现在只需要用2个。第三章链表、堆栈、队列3.2通过只调整链而不是数据来交换两个相邻的元素使用。a.单向链表b.双向链表(a)singlelinkedlists://beforepisthecellbeforethetwoadjacentcellsthataretobe//swapped//ErrorchecksareomittedforclarityvoidswapWithNext(Node*beforep){Node*p,*afterp;p=