数据结构习题答案13章.ppt

《数据结构习题答案13章.ppt》由会员分享，可在线阅读，更多相关《数据结构习题答案13章.ppt（33页珍藏版）》请在三一办公上搜索。

1、数据结构与算法分析,任务：,1.讲解第一次作业：1.7 1.8 1.11 2.82.做题：2.9 2.10 2.123.第二次作业：3.1 3.3 3.5 3.10然后讲解 2 和34.做题：3.4 3.16 3.17 3.18讲解4,1.7,Every problem certainly does not have an algorithm.As discussed in Chapter 15（p482 15.3),there are a number of reasons why this might be the case.Some problems dont have a suffic

2、iently clear definition.Some problems,such as the halting problem,are non-computable.For some problems,such as one typically studied by artificial intelligence researchers,we simply dont know a solution.,TheHaltingProblem是问，输入一段程序代码和一个针对此程序的输入，能否编程判断运行这个程序后程序是否会终止。这个问题的答案是否定的。也就是说，不可能有一种算法可以正确判断一个指定

3、的程序运行后，给予指定的输入，程序最后出不出得来。,村子里有个理发师，这个理发师有条原则是，对于村里所有人，当且仅当这个人不自己理发，理发师就给这个人理发。如果这个人自己理发，理发师就不给这个人理发。无法回答的问题是，理发师给自己理发吗？,1.8,We must assume that by“algorithm”we mean something composed of steps are of a nature that they can be performed by a computer.If so,than any algorithmcan be expressed in C+.,In

4、 particular,if an algorithm can be expressed in any other computer programming language,then it can be expressed in C+,since all(sufficiently general)computer programming languages compute the same set of functions.,1.11,Students at this level are likely already familiar with binary search.Thus,they

5、 should typically respond with sequential search and binary search.Binary search should be described as better since it typically needs to make fewer comparisons(and thus is likely to be much faster).,二分查找的时间复杂度：O(logn)顺序查找时间复杂度：O（n）二分：总共有n个元素，渐渐跟下去就是n,n/2,n/4,.n/2k，其中k就是循环的次数 由于你n/2k取整后=1即令n/2k=1可得

6、k=log2n,（是以2为底，n的对数）所以时间复杂度可以表示O()=O(log2n),2.8,long ifact(int n)/make n=0),n*fact(n-1)(n-1)*fact(n-2)(n-2)*fact(n-3)(n-3)*fact(n-4)(n-4)*fact(n-5).3*fact(3-1)2*fact(2-1)11*2*3*4*n=n!,2.9,void rpermute(int*array,int n)swap(array,n-1,Random(n);rpermute(array,n-1);,2.10,Fibr is so much slower than Fib

7、i because Fibr re-computes the bulk of the series twice to get the two values to add.What is much worse,the recursive calls to compute the subexpressions also re-compute the bulk of the series,and do so recursively.The result is an exponentialexplosion.In contrast,Fibi computes each value in the ser

8、iesexactly once,and so its running time is proportional to n.,并且在递归过程中,系统会建立堆栈来保存上一层状态信息,和退栈获取还原系统状态都要有开销的.系统做的事情不少,所以效率要低.递归：T(n)=O(1.618 n)迭代：T(n)=O(n),2.12,理论上：如果把double当成真正的实数，这个函数将无法退出，每次计算只是无限的接近0，而不可能等于0.实际执行过程中：double可以精确到小数点后14位，所以当执行一定的次数后，会超出double的精度，舍去精度之后的位数，变为0，从而退出函数。,3.1,Note that n

9、 is a positive integer.5n log n is most efficient for n=1.2n is most efficient when 2 n 4.10n is most efficient for all n 5.20n and 2n are never moreefficient than the other choices.,3.3,2 log3n log2n n2/3 20n 4n2 3n n!,3.5,假设Prunes 公司同类产品的微处理器运行速度为t，则有XYZ(t)=100 Prunes(t)当Prunes 公司同类产品一小时完成输入规模为n的程

10、序时则有Prunes(t)=n XYZ(t)=100n当Prunes 公司同类产品一小时完成输入规模为n2的程序时则有Prunes(t)=n2 XYZ(t)=100n2=(10n)2当Prunes 公司同类产品一小时完成输入规模为n3的程序时则有Prunes(t)=n3 XYZ(t)=100n3=(4.64n)3当Prunes 公司同类产品一小时完成输入规模为n!的程序时则有Prunes(t)=2n XYZ(t)=100*2nn+log100=n+6.64由司特林公式,3.10,(1)(n)(n2)(n2 log n).(n)（p64 rule2）,3.4,设运行速度为64倍的机器相应的输入规

11、模为n1，则有T(n1)=64T(n)因为采用相同的算法，所以T(n1)=64*3*2n转换成算法公式得T(n1)=26*3*2n=3*2n+6.由此得它在t秒内能解n+6的输入规模。同一的假设有T(n1)=64T(n)=64*n2=82*n2=(8n)2由此得它在t秒内能解8n的输入规模。,同一的假设有T(n1)=64*T(n)=64*8*=8*（64n）由此得它在t秒内能解64n的输入规模。,3.16,/Return position of first elem(if any)with value Kint newbin(int K,int*array,int left,int right

12、)int l=left-1;int r=right+1;while(l+1!=r)/Stop when l and r meetint i=(l+r)/2;/Look at middle of subarrayif(K arrayi)l=i;/In right half,if(r right)return ERROR;/K not in arrayif(arrayr!=K)return ERROR;/K not in arrayelse return r;/r at value K,3.17,int newbin(int K,int*array,int left,int right)/Retu

13、rn position of greatest element arrayi)l=i;/In right half,/Search value not in arrayif(l left)return ERROR;/No value less than Kelse return l;/l at first value less than K,3.18,we would initially search array positions 0,1,2,4,8,16,32and so on.Once we have found a value that is larger than or equal

14、to what we are searching for,we have bounded the subrange of the array from our last two searches,.The length of this subarray is at most n units wide,and we have done this initial bracketing in at most log n+1 searches.A normal binary search of the subarray will find the position n in an additional log n searches at most,for a total cost in O(log n)searches.,下次课或者下下次课需要一位同学讲栈，一位同学讲线性表，这周之内报名，给我或者杨老师报名都可以。讲课有平时成绩可以加。,Thanks!,