下载  >  课程资源  >  讲义  > 《数据结构与算法分析》答案

《数据结构与算法分析》答案 评分:

《数据结构与算法分析》第三版解答 带书签、非扫描版、中文版
19()(译者注:书中此题要证明∑F=F-2,而答案中证明的式子似乎是 ∑F=F2+2-2,不过只有形式上的区别)此题通过数学归纳法证明。N=12时, 命题显然成立,设命题对N=1,2,3,4…k均成立(k为正整数),因 k+1 ∑F=∑F+Fn,由归纳假设得等号右边的值为F+2-2+FH1=F+3-2,所 以对N-k+1命题也成立。因此对所有正整数N命题均成立。 (b)此题同样通过数学归纳法证明。注意到φ+1=02,即+02=1。对N=1或2 命题成立。假设N-1,2,k时命题均成立,由斐波那契数列的递推式 Fk-1=Fk t Fk 和归纳假设,可得 1<φ4+p41=(1+92)0+=9 由此命题得证 ()可参阋章末的任意一本数学参考文献。答案涉及到对生成函数的应用 10(∑(21-1)=2∑i-∑1=N(N+1)-N=N2 b)最简单的方法是通过数学归纳法证明。N=1的情况显然成立。其他情况, ∑?=(N+1)2+∑ i=1 (N+1)3+N(N+1) 4 (N+1)[+(N+1) (N+1)[ N2+4N+4 N+1)2(N+2) N+1)(N+2 i=1 第2章算法分析 2. 1 2/N, 37,NN, NloglogN, NlogN, Nlog(N), N., N2, NN N3,2"2,2。NogN与Nlog(N2)增长率相同 22(a)成立 (b)不成立,一个反例为T1(N)=2N,T2(N)=N,而f(N)=N ()不成立,一个反例为T(N)=N,2(N)=N,f(N)=N2 (d)不成立,反例如(c) 23NogN增长更慢,为证明这一点,我们使用反证法:假设N√mN比logN增长更 慢,两边同取对数,得到(e/√ogN)*ogN比 loglog增长更慢,第一个表达式实 际上是e√ogN,设L=gN,则有EL比lg增长得更慢,即e2 L Et log2L增 长的更慢,但实际上我们知道log2L=0(L),所以我们一开始的假设是错的,因此 命题得证。 24显然若k1<k2,则log4N=0(og2N),所以我们只需考虑k为正数的情况。对k=0 或k=1,命题显然成立。假设对k<1命题均成立,由 L'Hospital法则 lim g In N 由归纳假设,等号右边的极限为0,所以命题得证。(译者注:本书中log默认为以2为 底的对数,因此lgN求导应为2ogN 而不是g ,应是答案的错误 NIn 2 25定义当N为偶数时f(N)为1,N为奇数时f(N)为N,同样,定义当N为奇数时g(N)为 1,N为偶数时gN)为N,f(N)与g(N)的比值在0到∞间振荡。 2.6对下面的每个程序,做出的时间分析都与模拟结果一致 (1)运行时间为O(N) (2)运行时间为O(N2) 3)运行时间为O(N3) (4)运行时间为O(N2) (5)j最大可达到,最大可达到N2,k最大可达到j,即N2,因此可能的最大 的运行时间为NxN2x2,即O(N) 6)由前面的分析,i语句被执行O(N3)次,但实际上因为个j的取值中只有i个 使i语句为真,所以只有O(N2)次进入ⅱ语句内层,而每次执行内层循环的用时 为O(j)=O(N2),所以总共耗时为O(N4)。这个例子说明简单的把各层循环的 大小相乘有时会给出过高的估计结果。 27(a)显然三种算法都生成合法的置换,前两种算法有确保不会发生数字重复的检测,第 三种算法是打乱一个原本就没有重复的数组,所以三种都不会生成不合法的置换。前 两种算法是完全随机的,每种置换都是等可能的。而这一点对第三种算法(它由 R. Floyd提出)不是很显然,这一算法的正确性可以通过数学归纳法证明,读者可参 阅 Jon bentley的《 Programming Pearls》(《编程珠玑》) 需要指出的是若算法3的第二行改为 ap (Alil, A[RandInt(O, N-1)D); 则各置换并不随机出现。为了说明这一点,注意到当N=3时,共有27种等可能的交换 方式,而合法的置换有6种,无法平分27,因此若算法是如此,每种置换不会等可能 出现 (b)第一种算法,判断在A[i]位置随机生成的数是否与前面的重复需要耗费O(i)时间, 产生随机数个数的数学期望为N(N-i),这个值由如下的步骤得出:N个数中有个是 与前面重复的,所以产生一个不重复的数字的概率是N-i)N,且每次的结果互相独立 因此平均需要NN次尝试才能产生不重复的数字,所以时间界为 N-1 Ni N N ∑n:=N2∑=0(N2logN) =0 N 第二种算法节省了可能岀现的i次测试,所以时间界降为O(ⅥogN),第三种算法很明 显是线性的。 c:d)如果有足够的空间,运行结果会和上述的分析一致,如果没有足够的空间,第三 个算法当N很大时会有激烈的增长,使它看起来不是线性的, e)无法为第一、二种算法的最坏运行时间找到一个界,因为对任意给定的时间T,算 法结束的概率都不为υ(虽然如此,算法是一定会结束的)。第三种算法的最坏运行 时间仍是线性的,它的运行时间不依赖于产生的随机数序列。 28算法1:N-10.000时耗时约5天,N=100,000时耗时14.2年,N-1,00000耗时140 个世纪 算法2:N=100,000时耗时3小时,N=1,0000耗时2星期 算法3:N-1,000,000时耗时1.5分钟 这些计算都建立在电脑具有足够空间储存数组的前提下,算法4在N=1,0000时只 耗时3秒 29(a)O(N )O(N log N) 210(c)线性时间 211使用二分查找的变种可以得到O(ogN)的运行时间(假设数组已经预先读入) 13(a)首先判断N是否为奇数或2,然后判断是否能被3,5,,√N整除 ()假设每次除法均耗费一个单位时间,O(√N) (C)B=0(ogN) (dO(2 (e)如果20位的数需要时间为T,则4位的数需要时间为T2 f)B更合理,因为它更好的表达了输入的数据占据的空间大小 214该算法的运行时间为N乘以所有小于N的素数的倒数之和,为O( N log log n),详 见 Knuth《计算机程序设计艺术》第二卷 215依次计算出X2,X4,X,X1,X,X4,X的,最终算出X 216维护一个数组 PowersofX,它包含X,Ⅹ2,X4X 。N的二进制表示 可通过不断判断奇偶性并除以2得到)可用来选取数组中合适的项相乘得到结果。 217对N-0或N-1,乘法次数为0。对N>1,若b(N)为N的二进制表示中数字1的个数,则 乘法次数为 LOg N +b(N) 2.18(a)A (b)B (c)题中给出的信息不足以得出答案,因为我们只有最坏时间界 (d)否(答案原为"Yes",应该是答案有误) 219(a)当数组B中只有两个或更少的元素时递归便不必要了 (b)一种方法是,注意到如果前N-1个元素中有主要元素,则最后一个元素对结果没有影 响,否则最后一个元素可能是候选元,将它作为候选元。(译者疑问:可否比较AN2 和A及A1和A、是否相等,若有一组相等则加入B?) (c)设运行时间为T(N),有递推式T(N)=T(N/2)+O(N),解得T(N)=0(N)(参见第十章 102.1) (d保存一个数组A的拷贝后,可将要添加到数组B的元素直接覆盖在数组A上,每一级 递归均可这样做。最初的递归策略需要O(logN个数组,而这样只需要两个。 2.20如果不这样,我们可以巧妙地对数字编码,同时进行多个操作。例如,若 A-001,B-101,C-111,D=100,如果我们要计算A+B和C→D,只需要计算 00A00C+00B0UD即可。我们可以把这个方法推广到任意N对数字,在一个单位时间 內计算出每对的和。 222不能,若Low=1,High=2,则Md=1,递归永不会结束 224不能,和题2.22一样,递归可能永不会结束。 第3章表、栈和队列 3.2题3.4中关于抽象性程度的建议在本题中被应用。程序如图31所示,运行时间为 O(1+P PrintLotsd List L, List P) int Counter Position Lpos, Ppos Lpos=First(L) Ppos=First(P): Counter=1 whilc( i pos 1= null & ppos=nulL) If( Ppos->Element - Counter++ j printf(%0?",Lpos-i>Element ); Ppos= Next(Ppos, P); L Fig. 3.1. 33(a)对单链表,代码如图32所示 ,M BeforeP is the cell before the two adjacent cells that are to be swapped. * Error checks are omitted for clarity. h, Swap WithNcxt( Position cforcP, I ist L Pusiliun p aller P= BeforeP->Next. AfterP- P->Next: / Both p and after assumed not null,=k/ P->Next= AfterP-> Next BeforeP->Next- AfterP: AfterP->Next= p Fig, 3.2. 图中的注释为: Before为要交换的两个相邻元素之前的元素,为了代码的清晰错误检 查已被省略) (b)对双链表,代码如图3.3所示 /f P and after are cells to be switched. Error checks as before. F/ SwapwithNext( Position P List L Position before after Before= p->prey AfterP= P->Next P->Next- afterP-Next Beforep->Next after Afterp->Next=p. P->Nexl->Prev=P: P->Prey= A.fterP. Afterp->Prey= Before Fi.3.3. 图中注释为∶P和 After是要被交换的两个元素,错误处理同样已省略) 3.4求交集的函数 Intersect如下所示 /*This code can be made more abstract by uising operations such as W Retrieve and lsPastEnd to replace LiPos->Element and LIPos !=NULL A We have avoided this because these operations were not rigorously defined. Intersect( List Ll, List L2 List result Position li pos. l2pos resultpos LIPos=IIrst( LI );L2Pos=Iirst(L2); Result= MakcEmpty( NULL ) ResultPos= f'irst( Result while( lipos l-null & L2Pos -null) iff LIPos->Element L2 Pos->Element LIPos=Next( LIPos, LI else if( Ll Pos->Element> L2Pos->Element Pos=Next( L2Pos, L2 ): Insert( LlPos->Element, Result, ResultPos I 1 ) 1 2=Ncxt( 1. 2Pos, 1. 2); ResultPos= Next( ResultPos, Rcsult return Result 图中注释为:这个代码可以通过用 Retrieve和 IsPastend替代L1Pos-> Element和 L1Pos!」=NULL的方法拥有更大的抽象性。我们不这样做是因为这些操作没有被严密定义) 3.5求并集的函数 Union如图34所示: List Union( List ll, List L2 List resull: ElementType InsertElement Position li pos. l2pos resultpos LIPos=First( LI ) L2Pos=First(L2); Result MakeEmpty( NULL ResultPos= First( result ) while( lipos != null & L2pos!null )i if( LIPos->Element L2PoS->Element Insertllement=LIPos->lement. LIPus= Nexl( LIPus, L1); else if( LIPos->Element >L2PoS->Element ) Insertelement= L2 Pos->Element L2Pos=Next( L2Pos, L2 Insertelement= LI Pos->Element L IPos=Next( L IPos, I 1): 1.2Pos= Ncxt( I 2Pos, 12); Insert( InsertElement, Result, ResultPos ResultPos= Next( ResulLPos, Resull y Flush out remaining list */ while( ll Pos ]= null )i Insert(LIPos->Element, Result, Result Pos ) LIPus=Nexl( LI Pos, L1 ) ResulLPos= Next( ResulLPos, Result while( l2pos!= null )1 Insert( 1,2Pos->Flcmcnt, Rcsult, Rcsu ltPos L2Pos- Next( L2Pos, L2 ) ResultPos= Next( ResultPos, Result ) return result. Fig·3.4 3.7(a)一种算法是在计算的过程中始终保持结果按幂排列。MN个乘积中每一个都需要对 列表进行一次搜索以在有同类项时直接合并。因为链表的大小为O(MN),总运行时间 为O(M2N2) (c) O(MNIogMN)的解法可以通过先计算出所有MN对的乘积,再用第七章的任意一个 算法把它们按幂排列。之后可以很轻易的合并同类项。 (d算法的选择取决于M和N的相对大小,如果它们很接近那么(o)的算法更好,如果 有一个多项式十分短小,那么(b)的算法更好

...展开详情
2018-08-10 上传 大小:1.31MB
举报 收藏
分享
张乃孝数据结构与算法全集

本资源包含了三个张乃孝老师的文档: 数据结构与算法课件, 数据结构与算法C语言描述, 数据结构与算法学习辅导及习题详解, 文中有大量例题与习题, 并附有解答, 是学习算法与数据结构必备的资源

立即下载
数据结构与算法课程设计要求

关于《数据结构与算法》课程设计要求,以及c源程序代码,图书管理系统设计。

立即下载
Python数据结构与算法(英文)

Python数据结构与算法(英文) Data Structures and Algorithms with Python

立即下载
《数据结构与算法分析》答案

《数据结构与算法分析》第三版解答 带书签、非扫描版、中文版

立即下载
数据结构与算法(C++)中文版

如题,数据结构与算法(C++)中文版书本的电子版,PDF文件。

立即下载
数据结构与算法 C#语言描述源代码

《数据结构与算法 C#语言描述》Michael McMillan 著。这本书的主要源代码,本人在学习这本书的一周中自己按书中所举得例子,敲到VS2008上的。都可以运行,但由于以说明问题为主,考虑不是很全面,当然有Bug也是不可避免的,如想把例子用于实际必须经过细心的调试。希望能对大家有所帮助。

立即下载
数据结构与算法分析:C语言描述 中文版

C语言版数据结构与算法,圣经级教程,全面深入。Mark Allen Weiss 著。

立即下载
数据结构与算法(中文版4本).rar

本资源包共有4本电子书,数据结构和算法相关,建议转行计算机的必读必学!数据结构和算法十分重要!书一《数据结构与算法分析-C++语言描述(第四版)》、书二《算法(第4版)(java版)》、书三《算法与数据结构(python版)(北大内部教材)》、书四《数据结构与算法分析-C语言描述(第二版)》

立即下载
殷人昆-数据结构

殷人昆-数据结构

立即下载
数据结构与算法Java语言版第二版Adam Drozdek

本代码是Adam Drozdek所著《数据结构与算法Java语言版》第二版的所有源代码,欢迎各位下载调试。

立即下载
数据结构模拟题

大连理工软件学院数据结构老师给的最后的期末模拟试题

立即下载
图结构实验 数据结构 最短路径

数据结构中有关图结构的实验报告,里面包含图结构基本编程实现和最短路径算法实现,完整代码均附在报告中。

立即下载
数据结构与算法之美 完整版 全部资料 + 音频

开篇词 | 从今天起,跨过“数据结构与算法”这道坎 01 | 为什么要学习数据结构和算法? 02 | 如何抓住重点,系统高效地学习数据结构与算法? 03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗? 04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度 不定期福利第一期 | 数据结构与算法学习书单 05 | 数组:为什么很多编程语言中数组都从0开始编号? 06 | 链表(上):如何实现LRU缓存淘汰算法? 07 | 链表(下):如何轻松写出正确的链表代码? 08 | 栈:如何实现浏览器的前进和后退功能? 09 | 队列:队列在线程池等有限资源池中的应用 10 |

立即下载
《数据结构与算法(C#语言描述)》源码

此为数据结构与算法(C#语言描述) 一书的部分源码 本书是在.NET框架下用C#语言实现数据结构和算法的第一本全面的参考书。本书介绍的方法非常实用,采用了时间测试而非大O表示法来分析算法性能。内容涵盖了数据结构和算法的基本原理,涉及数组、广义表、链表、散列表、树、图、排序搜索算法以及更多概率算法和动态规则等高级算法。此外,书中还提供了.NET框架类库中的C#语言实现的数据结构和算法。 本书适合作为C#数据结构课程的教材,同时也适合C#专业人士阅读。

立即下载
l数据结构学习资源

本视频是用于刚刚入门学习数据结构的同学,希望能学到一些数据结构基础

立即下载
数据结构java语言版

Java版数据结构,你值得拥有

立即下载
数据结构与 (java语言描述)第二版(源代码)

数据结构与 (java语言描述)第二版(源代码) 【原 书 名】 Data Structures and Abstractions with Java (2nd Edition) 【原出版社】 Prentice Hall 【作  者】(美)Frank M.Carrano [同作者作品] 【译  者】 金名[同译者作品] 【丛 书 名】 世界著名计算机教材精选

立即下载
数据结构上机实验答案

数据结构上机实验答案,调试好的,线性表,队列,冒泡排序,希尔排序,快速排序,哈夫曼树相关实验.有详细的程序注释.

立即下载
数据结构哈希表设计与实现课程设计

是武汉理工大学的数据结构哈希表课程设计,文档可以直接拿去用啦,都不用修改的啊,很给力哦亲!我也是辛苦一番啦,希望能帮到你啊

立即下载
数据结构-顺序队列

1、实现顺序队列相关API函数 2、泛型编程思想,由主调函数提供内存空间 3、实体数据可以是基本类型或者复合类型 4、遍历时,使用回调函数。实现“策略”与“机制”分离

立即下载