数据结构与算法分析_java语言描述课后习题答案.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：3.16M 资料格式：pdf 举报版权申诉

qq_36361799-9747906-4744300845397447122.pdf-第1页.png

第1页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第2页.png

第2页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第3页.png

第3页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第4页.png

第4页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第5页.png

第5页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第6页.png

第6页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第7页.png

第7页 / 共105页

qq_36361799-9747906-4744300845397447122.pdf-第8页.png

第8页 / 共105页

文本预览

Weiss Java Solutions pages p. i (front) Windfall Software, PCA ZzTEX 12.2

Publisher Greg Tobin Executive Editor Michael Hirsch Editorial Assistant Lindsey Triebel Marketing Manager Michelle Brown Marketing Assistant Dana Lopreato Digital Asset Manager Marianne Groth Composition Windfall Software, using ZzTEX Access the latest information about Addison-Wesley titles from our World Wide Web site: http://www.aw- bc.com/computing Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. Copyright © 2007 by Pearson Education, Inc. For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc., Rights and Contract Department, 75 Arlington Street, Suite 300, Boston, MA 02116 or fax your request to (617) 848-7047. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or any other media embodiments now known or hereafter to become known, without the prior written permission of the publisher. Printed in the United States of America. 1 2 3 4 5 6 7 8 9 10—PDF— 9 08 07 06 Weiss Java Solutions pages p. ii (front) Windfall Software, PCA ZzTEX 12.2

C O N T E N T S Preface Chapter 1 Introduction Chapter 2 Algorithm Analysis Chapter 3 Lists, Stacks, and Queues Chapter 4 Trees Chapter 5 Hashing Chapter 6 Priority Queues (Heaps) Chapter 7 Sorting Chapter 8 The Disjoint Set Class Chapter 9 Graph Algorithms Chapter 10 Algorithm Design Techniques Chapter 11 Amortized Analysis Chapter 12 Advanced Data Structures and Implementation v 1 3 7 29 47 53 61 67 71 85 95 99 Weiss Java Solutions pages p. iii (front) iii Windfall Software, PCA ZzTEX 12.2

Weiss Java Solutions pages p. iv (front) Windfall Software, PCA ZzTEX 12.2

P R E F A C E 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 reﬂect the state of the book in the ﬁrst printing of the second edition. Speciﬁcally omitted are general programming 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@ﬁu.edu. Weiss Java Solutions pages p. v (front) v Windfall Software, PCA ZzTEX 12.2

Weiss Java Solutions pages p. vi (front) Windfall Software, PCA ZzTEX 12.2

C H A P T E R 1 Introduction 1.4 The general way to do this is to write a procedure with heading void processFile( String fileName ); which opens ﬁleName, does whatever processing is needed, and then closes it. If a line of the form #include SomeFile is detected, then the call processFile( SomeFile ); is made recursively. Self-referential includes can be detected by keeping a list of ﬁles for which a call to processFile has not yet terminated, and checking this list before making a new call to processFile. 1.5 1.7 1.8 1.9 1.10 public static int ones( int n ) { if( n < 2 ) return n; return n % 2 + ones( n / 2 ); } 42 4 43 + 3 + 2 + 9 42 (a) The proof is by induction. The theorem is clearly true for 0 < X ≤ 1, 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 ﬁrst inequality follows by the inductive hypothesis. B = 2XB. Thus log AB = XB. Since X = log A, the theorem is proved. (b) Let 2X = A. Then AB = (2X) (a) The sum is 4/3 and follows directly from the formula. + 2 (b) S = 1 gives 3S = 1+ 1 (c) S = 1 + 4 second gives 3S = 1+ 3 2(4/9) + 4/3 = 20/9. Thus S = 20/27. (d) Let SN N − N/2−1 of SN−1, SN−2, . . . , S0 and solve the recurrence. Solving the recurrence is very difﬁcult. i=1 i=N/2 24 = 16 ≡ 1 (mod 5). (24) + . . .. Subtracting the ﬁrst equation from the second + . . .. Subtracting the ﬁrst equation from the + 16 4i . Thus 3S = iN 4i . Follow the same method as in parts (a)–(c) to obtain a formula for SN in terms 25 ≡ 125 (mod 5). Thus 2100 ≡ 1 (mod 5). + 3 + . . .. 4S = 1+ 2 + . . .. By part (a), 3S = 4/3 so S = 4/9. + . . .. 4S = 1+ 4 + 9 + . . .. Rewriting, we get 3S = 2 = ∞ = N i=0 ≈ ln N − ln N/2 ≈ ln 2. ∞ i=0 + ∞ i=0 + 5 42 + 7 43 i=1 42 43 4 42 4 4 4 42 43 1 i 1 i i 4i 1 4 1 i Weiss Java Solutions pages p. 1 (chap01) Windfall Software, PCA ZzTEX 12.2 1

Introduction Chapter 1 (a) Proof is by induction. The statement is clearly true for N = 1 and N = 2. Assume true for + Fk+1. By the induction hypothesis, the value of the sum N = 1, 2, . . . , k. Then − 2, where the latter equality follows from the deﬁnition of on the right is Fk+2 the Fibonacci numbers. This proves the claim for N = k + 1, and hence for all N. (b) As in the text, the proof is by induction. Observe that φ + 1= φ2. This implies that φ −1+ φ −2 = 1. For N = 1 and N = 2, the statement is true. Assume the claim is true for N = 1, 2, . . . , k. = k Fi Fi i=1 = Fk+3 − 2 + Fk+1 k+1 i=1 = Fk + Fk−1 Fk+1 by the deﬁnition, and we can use the inductive hypothesis on the right-hand side, obtaining Fk+1 < φk + φk−1 −1φk+1 + φ −1 + φ < φ Fk+1 < (φ −2φk+1 −2)φk+1 < φk+1 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. 2 1.11 1.12 N i=1 (2i − 1) = 2 i − N N i=1 (a) (b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise, i=1 4 i3 i=1 1= N(N + 1) − N = N2. i3 = (N + 1)3 + N N+1 i=1 = (N + 1)3 + N2(N + 1)2 + (N + 1) = (N + 1)2 N2 4 N2 + 4N + 4 = (N + 1)2 = (N + 1)2(N + 2)2 (N + 1)(N + 2) = N+1 i=1 = 22 2 2 4 2 i Weiss Java Solutions pages p. 2 (chap01) Windfall Software, PCA ZzTEX 12.2

分享到：

赞收藏

资料库

数据结构与算法分析_java语言描述课后习题答案.pdf

相关推荐

课程资源

热门标签

最新资料