《数据结构与算法分析—c语言描述_课后答案 (2)》由会员分享，可在线阅读，更多相关《数据结构与算法分析—c语言描述_课后答案 (2)（69页珍藏版）》请在金锄头文库上搜索。
1、Data Structures and Algorithm Analysis in C (second edition) Solutions Manual Mark Allen Weiss Florida International University Preface Included in this manual are answers to most of the exercises in the textbook Data Structures and Algorithm Analysis in C, second edition, published by Addison-Wesle
2、y. These answers refl ect the state of the book in the fi rst printing. Specifi cally omitted are likely programming assignments and any question whose solu- tion is pointed to by a reference at the end of the chapter. Solutions vary in degree of complete- ness; generally, minor details are left to
3、the reader. For clarity, programs are meant to be pseudo-C rather than completely perfect code. Errors can be reported to weissfi u.edu. Thanks to Grigori Schwarz and Brian Harvey for pointing out errors in previous incarnations of this manual. Table of Contents 1. Chapter 1: Introduction 1 2. Chapt
4、er 2: Algorithm Analysis 4 3. Chapter 3: Lists, Stacks, and Queues .7 4. Chapter 4: Trees .14 5. Chapter 5: Hashing 25 6. Chapter 6: Priority Queues (Heaps) .29 7. Chapter 7: Sorting 36 8. Chapter 8: The Disjoint Set ADT .42 9. Chapter 9: Graph Algorithms .45 10. Chapter 10: Algorithm Design Techniq
5、ues 54 11. Chapter 11: Amortized Analysis 63 12. Chapter 12: Advanced Data Structures and Implementation 66 -iii- Chapter 1: Introduction 1.3Because of round-off errors, it is customary to specify the number of decimal places that should be included in the output and round up accordingly. Otherwise,
6、 numbers come out looking strange.We assume error checks have already been performed; the routine Separate? is left to the reader. Code is shown in Fig. 1.1. 1.4The general way to do this is to write a procedure with heading void ProcessFile( const char *FileName ); which opens FileName,? does whate
7、ver 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 fi les for which a call to ProcessFile? has not yet terminated, and checking t
8、his list before making a new call to ProcessFile.? 1.5(a) The proof is by induction. The theorem is clearly true for 0 0 ) putchar(.); PrintFractionPart( FractionPart, DecPlaces ); Fig. 1.1. _ _ _ _ 1.7 i?=?N?/ 2? N i 1 _ = i?=1 N i 1 _ i?=1 ?N?/ 2 1? i 1 _ ln N? ln N?/ 2 ln 2. -2- 1.824 = 16 1 (mod
9、? 5). (24)25 125 (mod? 5). Thus 2100 1 (mod? 5). 1.9(a) Proof is by induction. The statement is clearly true for N? = 1 and N? = 2. Assume true for N? = 1, 2, ., k?. Then i?=1 k?+1 Fi? = i?=1 k Fi?+Fk?+1. By the induction hypothesis, the value of the sum on the right is Fk?+2 2 + Fk?+1= Fk?+3 2, whe
10、re the latter equality follows from the defi nition of 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
11、is true for N? = 1, 2, ., k?. Fk?+1 = Fk? + Fk?1 by the defi nition and we can use the inductive hypothesis on the right-hand side, obtaining Fk?+1 1, the number of multiplies used is ?log N? + b?(N?) 1 2.18 (a) A?. (b) B?. (c) The information given is not suffi cient to determine an answer. We have
12、 only worst- case bounds. (d) Yes. 2.19 (a) Recursion is unnecessary if there are two or fewer elements. (b) One way to do this is to note that if the fi rst N?1 elements have a majority, then the last element cannot change this. Otherwise, the last element could be a majority. Thus if N? is odd, ig
13、nore the last element. Run the algorithm as before. If no majority element emerges, then return the N?th?element as a candidate. (c) The running time is O?(N?), and satisfi es T?(N?) = T?(N?/ 2) + O?(N?). (d) One copy of the original needs to be saved. After this, the B? array, and indeed the recur-
14、 sion can be avoided by placing each Bi?in the A? array. The difference is that the original recursive strategy implies that O?(log N?) arrays are used; this guarantees only two copies. 2.20 Otherwise, we could perform operations in parallel by cleverly encoding several integers into one. For instan
15、ce, if A = 001, B = 101, C = 111, D = 100, we could add A and B at the same time as C and D by adding 00A00C + 00B00D. We could extend this to add N? pairs of numbers at once in unit cost. 2.22 No. If Low? = 1, High? = 2, then Mid? = 1, and the recursive call does not make progress. 2.24 No. As in Exercise 2.22, no progress is made. -6- Chapter 3: Lists, Stacks, and Queues 3.2The comments for Exercise 3.4 regarding the amount of abstractness used apply here. The running time of the procedure in Fig. 3.1 is O?(L? + P?). _ _
