《c中的数据结构与算法分析》由会员分享，可在线阅读，更多相关《c中的数据结构与算法分析（69页珍藏版）》请在金锄头文库上搜索。
1、Data StructuresandAlgorithm Analysis in CSecond EditionSolutions ManualMark Allen Weiss Florida International UniversityPrefaceIncluded in this manual are answers to most of the exercises in the textbook Data Structures andAlgorithm Analysis in C, second edition, published by Addison-Wesley. These a
2、nswers reflectthe state of the book in the first printing.Specifically 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 the reader. For
3、 clarity, programs are meant to be pseudo-C rather than completely perfect code.Errors can be reported to weissfiu.edu. Thanks to Grigori Schwarz and Brian Harvey for pointing out errors in previous incarnations of this manual.Table of Contents1. Chapter 1: Introduction .12. Chapter 2: Algorithm Ana
4、lysis .43. Chapter 3: Lists, Stacks, and Queues .74. Chapter 4: Trees .145. Chapter 5: Hashing .256. Chapter 6: Priority Queues (Heaps) .297. Chapter 7: Sorting .368. Chapter 8: The Disjoint Set ADT .429. Chapter 9: Graph Algorithms .4510. Chapter 10: Algorithm Design Techniques .5411. Chapter 11: A
5、mortized Analysis .6312. Chapter 12: Advanced Data Structures and Implementation .66-iii-Chapter 1: Introduction1.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, numbers come out looking
6、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 headingvoid ProcessFile( const char *FileName );which opens FileName,? does whatever processing is needed, and
7、 then closes it. If a line of the form#include SomeFileis detected, then the callProcessFile( SomeFile );is made recursively. Self-referential includes can be detected by keeping a list of files for which a call to ProcessFile? has not yet terminated, and checking this list before making a new call
8、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?Ni1 _= i?=1Ni1 _ i?=1?N?/ 2 1?i1 _ ln N? ln N?/ 2 ln 2.-2-1.824 = 16 1 (mod? 5). (24)25 125 (mod? 5). Thus 2100 1 (mod? 5).1.9
9、(a) Proof is by induction. The statement is clearly true for N? = 1 and N? = 2. Assume truefor N? = 1, 2, ., k?. Then i?=1k?+1 Fi? = i?=1k Fi?+Fk?+1. By the induction hypothesis, the value of thesum on the right is Fk?+2 2 + Fk?+1= Fk?+3 2, where the latter equality follows from thedefinition of the
10、 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?.Fk?+1 = Fk? + Fk?1by the defin
11、ition and we can use the inductive hypothesis on the right-hand side, obtainingFk?+1 1, the number of multiplies used is?log N? + b?(N?) 12.18 (a) A?.(b) B?.(c) The information given is not sufficient to determine an answer. We have only worst- case bounds.(d) Yes.2.19 (a) Recursion is unnecessary i
12、f there are two or fewer elements.(b) One way to do this is to note that if the first 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, ignore 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 satisfies T?(N?) = T?(N?/ 2) + O?(N?).(d
