数据结构与算法 java版本

所需积分/C币:41 2017-08-18 18:25:49 3.16MB PDF
收藏 收藏 2
举报

数据结构与算法中的java版本,相比于c版本,对java学习者更有用处
CONTENTS Preface Chapter 1 Introduction Chapter 2 algorithm analysis 3 Chapter 3 Lists, Stacks, and Queues Chapter 4 Trees 29 Chapter 5 Hashing 47 Chapter 6 Priority Queues(Heaps 53 Chapter 7 Sorting 61 Chapter 8 the disjoint Set class 67 Chapter 9 Graph algorithms Chapter 10 Algorithm Design Techniques 85 Chapter 11 Amortized Analysis 95 Chapter 12 Advanced data Structures and Implementation 99 i Weiss Java Solutions pages p i( front) Windfall Software, PCA ZZ EX 12.2 Weiss Java Solutions pages p iv(front) Windfall Software, PCA ZZ EX 12.2 PREFACE Included in this manual are answers to many of the exercises in the textbook data Structures and Algorithm Analysis in Java, second edition, published by Addison-Wesley. These answers reflect the state of the book in the first printing of the second edition Specifically omitted are general programning questions and any question whose solution is pointed to by a reference at the end of the chapter Solutions vary in degree of completeness: generally, minor details are left to the reader: For clarity. the few code segments that are present are meant to be pseudo-Java rather than completely perfect code Errors can be reported to weiss@fiu. edu Weiss Java Solutions pages pv(front) Windfall Software, PCA ZZ EX 12.2 Weiss Java Solutions pages p vi(front) Windfall Software, PCA ZZ EX 12.2 CHAPTE R Introduction 1.4 The general way to do this is to write a procedure with heading void processfile( string fileName which opens filename, does whatever processing is needed, and then closes it. If a line of the form #include some fil is detected. then the call processfile( Somefile ) is made recursively. Self-referential includes can be detected by keeping a list of files for which a ca to processFile has not yet terminated, and checking this list before making a new call to processFile public static int ones( int n) f(n<2) return n名2+ones(n/2) I7(a)The proof is by induction. The theorem is clearly true for 0 < X< l, since it is true for X=1 and for X 1, log X is negative. It is also easy to see that the theorem holds for 1 X< 2, since it is true for X= 2, and for X 2, log X is at most 1. Suppose the theorem is true for p <X < 2p (where p is a positive integer), and consider any 2p<Y<4p(p 1). Then log Y=1+ log(Y/2)< 1+Y/2<Y/2+Y/2<Y, where the first inequality follows by the inductive hypothesis (b) Let 2X=A. Then A=(2%)=2B. Thus log a=XB. Since X= log A, the theorem is proved 1. 8 (a) The sum is 4/3 and follows directly from the formula (b)S=+++……4S=1+++… Subtracting the first equation from the second gives 35=1+f+++.. By part (a), 35=4/3 5=4 /9 (C)S=+4+4+…4S=1++平+4+… Subtracting the first equation from the second gives 3S=1+4+2+43+.. Rewriting, we get 3S=2 2 x+∑1.Thus3S= 2(4/9)+4/3=20/9. Thus s=20/27 (d) Let Sn=>A. Follow the same method as in parts (a)-(c)to obtain a formula for SN in terms of SN-1, SN-2,.., So and solve the recurrence. Solving the recurrence is very difficult LN/2-1」 1.9 ∑}≈lnN-lnN/2≈ln2 i=LN/2」1 1.102+=16=1(umod5).(24)2=125(mod5).Thus200=1(md5 Weiss Java Solutions pages p 1(chap01) Windfall Software, PCA ZZ EX 12.2 2 Chapter 1 Introducti I.l(a) Proof is by induction. The statement is clearly true for N= l and N= 2. Assume true for N =1, 2,.,k. Then 2F=2F+Fn+1. By the induction hypothesis, the value of the sum on the right is Fk+2-2+ Fn+1=Fk+3-2, where the latter equality follows from the definition of the Fibonacci numbers. This proves the claim for N =k+ l, and hence for all N (b)Asin the text, the proof is by induction. Observe that +1=p. This implies that p +o2 1. For N=l and N=2. the statement is true. Assume the claim is true for N=1.2.. k k+1 by the definition, and we can use the inductive hypothesis on the right-hand side, obtaining 1<y+φ and proving the theorem (c) See any of the advanced math references at the end of the chapter. the derivation involves the use of generating functions 112(a)∑(21-1)=2∑t-∑1=N(N+1)-N=N2 (b) The easiest way to prove this is by induction. The case n=l is trivial. Otherwise ∑P=(N+1)+∑ =(N+1)3+N(N+1)2 (N+)2/ (N+1) =(N+1) 2+4N+4 (N+1)2(N+2 (N+1)(N+2)]2 Weiss Java Solutions pages p2(chap01) Windfall Software, PCA ZZ EX 12.2 CHAPTE R Algorithm Analysis 2.1 2/N, 37, VN, N, N loglog n, n log N, N log(n ), N log N, N,, N2, N logN, N, 212, 2 n log n and n log(n) grow at the same rate 2.2(a) True (b)False. A counterexample is TI(N)=2N, T2(N)=N, and f(N)=N (c) False. A counterexample is T,(N)=N2, T2(N)=N, and f(N)=N2 (d)False. The same counterexample as in part(c)applies 2.3 We claim that n log n is the slower growing function. To see this, suppose otherwise. Then, Ns)Job A would grow slower than log N. Taking logs of both sides, we find that, under this assumption E/log n log n grows slower than log log N. But the first expression simplifies to EVlog N. If L=log n, then we are claiming that evl grows slower than log l, or equivalently, that E L grows slower than log [. But we know that log L.=o(L), so the original assumption is false, proving the claim 2.4 Clearly, log"=o(log 2 N)if k1 < k2, so we need to worry only about positive integers. The claim early true for k=o and k= l Suppose it is true for k< i. Then, by L Hopitals rule, li g lim log →o N N→∞ The second limit is zero by the inductive hypothesis, proving the claim 2.5 Let f(N)= l when N is even, and n when N is odd. Likewise, let g(N)=l when N is odd, and N when N is even. Then the ratio f(N)/g(N)oscillates between O and inf 2.6(a)2 (b)o(loglog d) 2.7 For all these programs, the following analysis will agree with a simulation (1) The running time is O(N) (In) The running time is O(N2) (Ill) The running time is O(N) (IV) The running time is O(N2) (v)jcan be as large as i, which could be as large as N. k can be as large as j, which is N. The running time is thus proportional to N N2 N2, which is O(N) (VI) The if statement is executed at most N times, by previous arguments, but it is true only O(N2 times(because it is true exactly i times for each i). Thus the innermost loop is only executed O(N) Weiss Java Solutions pages p 3(chap02) Windfall Software, PCA ZZ EX 12.2 Chapter 2 Algorithm Analysis times. Each time through. it takes O(4)=O(N)time, for a total of O(Nt). This is an example where multiplying loop sizes can occasionally give an overestimate 2. 8 (a) It should be clear that all algorithms generate only legal permutations. The first two algorithms have tests to guarantee no duplicates; the third algorithm works by shuffling an array that initially has no duplicates, so none can occur. It is also clear that the first two algorithms are completely random and that each permutation is equally likely. The third algorithm, due toR. Floyd, is not as obvious the correctness can be proved by induction. See J. Bentley, " Programming Pearls, "Communications of the ACM 30(1987), 754-757. Note that if the second line of algorithm 3 is replaced with the statement swapReferences( ali], a[ randInt( 0, n-1 )J then not all permutations are equally likely. To see this, notice that for n=3, there are 27 equally likely ways of performing the three swaps, depending on the three random integers. Since there are only 6 permutations, and 6 does not evenly divide 27, each permutation cannot possibly be equall represented (b) For the first algorithm, the time to decide if a random number to be placed in alil has not been used earlier is O(i). The expected number of random numbers that need to be tried is N/(N-i) This is obtained as follows: i of the N numbers would be duplicates. Thus the probability of success Is(N-D/N. Thus the expected number of independent trials is N/(N-i). The time bound is thus ∑x:≤∑ ∑ ∑2=0 The second algorithm saves a factor of i for each random number, and thus reduces the time bound to o(n log n) on average. The third algorithm is clearly linear (c, d) The running times should agree with the preceding analysis if the machine has enough memor If not, the third algorithm will not seem linear because of a drastic increase for large n (e)The worst-Case running time of algorithms I and II cannot be bounded because there is always a finite probability that the program will not terminate by some given time T. The algorithm does however, terminate with probability 1. The worst-case running time of the third algorithm is linear s running time does not depend on the sequence of random numbers 2.9 Algorithm 1 at 10,000 is about 38 minutes and at 100,000 is about 26 days. Algorithms 1-4 at I million are approximately: 72 years, 4 hours, 0. 7 seconds, and 0.03 seconds respectively. These calculations assume a machine with enough memory to hold the entire array. 2.10(a)O(N) (c)The answer depends on how many digits past the decimal point are computed. Each digit costs O(N) 2.11 (a) Five times as long, or 2.5 ms (b) Slightly more than five times as long (c)25 times as long, or 12.5 ms (d)125 times as long, or 62.5 ms 2.12 (a)12000 times as large a problem, or input size 1, 200,000 (b)input size of approximately 425,000 Weiss Java Solutions pages p 4(chap02) Windfall Software, PCA ZZ EX 12.2

...展开详情
试读 105P 数据结构与算法 java版本
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    一个资源只可评论一次,评论内容不能少于5个字
    芝芝111 没有讲解,不好
    2019-06-26
    回复
    m0_37799174 很不错,资源很好
    2018-03-05
    回复
    TruthTeng 资源很好,受用
    2018-02-28
    回复
    nnzz2008 不小心把密码删了- -
    2018-02-26
    回复
    r_obery 资源很好,学习了
    2018-02-01
    回复
    img
    Mooneal

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    数据结构与算法 java版本 41积分/C币 立即下载
    1/105
    数据结构与算法 java版本第1页
    数据结构与算法 java版本第2页
    数据结构与算法 java版本第3页
    数据结构与算法 java版本第4页
    数据结构与算法 java版本第5页
    数据结构与算法 java版本第6页
    数据结构与算法 java版本第7页
    数据结构与算法 java版本第8页
    数据结构与算法 java版本第9页
    数据结构与算法 java版本第10页
    数据结构与算法 java版本第11页
    数据结构与算法 java版本第12页
    数据结构与算法 java版本第13页
    数据结构与算法 java版本第14页
    数据结构与算法 java版本第15页
    数据结构与算法 java版本第16页
    数据结构与算法 java版本第17页
    数据结构与算法 java版本第18页
    数据结构与算法 java版本第19页
    数据结构与算法 java版本第20页

    试读已结束,剩余85页未读...

    41积分/C币 立即下载 >