数据结构与算法习题讲解(全)电子教案.ppt

《数据结构与算法习题讲解(全)电子教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章1.5编写一个递归方法，它返回数n的二进制表示中1的个数。利用这样的事实：如果n是奇数，那么它等于n/2的二进制表示中1的个数加1。①intones(intn){if(n<2)returnn;returnn%2+ones(n/2);}②#includeusingnamespacestd;intj=0;count(intn){intk;k=n/2;j++;while(k>=1){if(n%2==0)j--;returncount();}}main(){inti,j;cout<<“Pleas

2、einputn:”<>i;if(i<0)i=-i;count(i);cout<<“所输入整数中的二进制中1的个数是：”<0成立①数学归纳法：当0

3、1+y/2x即2x>x,得logx

4、哪些函数以相同的增长率增长。答：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)

5、+;for(j=0;j

6、O(N5).6)sum=0;for(i=1;i

7、这段程序段的循环次数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

8、)，但是要使用一个附加的数组，称之为used数组。当一个随机数ran最初被放入数组a的时候，设置used[ran]=ture。就是说，当一个随机数填入a[i]时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样可能用i步来测试；(3).填写该数组，使得a[i]=i+1，然后for(i=1;i