数据结构与算法分析—c语言描述_课后答案

《数据结构与算法分析—c语言描述_课后答案》由会员分享，可在线阅读，更多相关《数据结构与算法分析—c语言描述_课后答案（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 reflect the 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

3、 reader. For 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 Contents 1. Chapter 1: Introduction . 1 2. Chapter

4、 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

5、 Techniques . 54 11. Chapter 11: Amortized Analysis . 63 12. Chapter 12: Advanced Data Structures and Implementation . 66 -iii- Chapter 1: Introduction 1.3 Because of round-off errors, it is customary to specify the number of decimal places that should be included in the output and round up accordin

6、gly. Otherwise, numbers come out looking strange. We assume error checks have already been performed; the routine SeparateC| is left to the reader. Code is shown in Fig. 1.1. 1.4 The general way to do this is to write a procedure with heading void ProcessFile( const char *FileName ); which opens Fil

7、eName,C| 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 files for which a call to ProcessFileC| has not yet termina

8、ted, and checking this list before making a new call to ProcessFile.C| 1.5 (a) The proof is by induction. The theorem is clearly true for 0 XC| 1, since it is true for XC| = 1, and for XC| 1, log XC| is negative. It is also easy to see that the theorem holds for 1 XC| 2, since it is true for XC| = 2

9、, and for XC| 2, log XC| is at most 1. Suppose the theorem is true for pC| XC| 2pC| (where pC| is a positive integer), and consider any 2pC| YC| 4pC| (pC| 1). Then log YC| = 1 + log (YC| / 2) 1 + YC| / 2 YC| / 2 + YC| / 2 YC|, where the first ine- quality follows by the inductive hypothesis. (b) Let

10、 2 XC| = AC|. Then A C|BC| = (2 XC| ) BC| = 2 XBC| . Thus log A C|BC| = XBC|. Since XC| = log AC|, the theorem is proved. 1.6 (a) The sum is 4/3 and follows directly from the formula. (b) SC| = 4 1 _ + 4 2 2 _ + 4 3 3 _ + . . . .4SC| = 1+ 4 2 _ + 4 2 3 _ + . . . . Subtracting the first equation from

11、 the second gives 3SC| = 1 + 4 1 _ + 4 2 2 _ + . . . . By part (a), 3SC| = 4/ 3soSC| = 4/ 9. (c) SC| = 4 1 _ + 4 2 4 _ + 4 3 9 _ + . . . .4SC| = 1 + 4 4 _ + 4 2 9 _ + 4 3 16 _ _ + . . . . Subtracting the first equa- tion from the second gives 3SC| = 1+ 4 3 _ + 4 2 5 _ + 4 3 7 _ + . . . . Rewriting,

12、we get 3SC| = 2 iC|=0 4 iC| i _ + iC|=0 4 iC| 1 _ . Thus 3SC| = 2(4/ 9) + 4/ 3 = 20/ 9. Thus SC| = 20/ 27. (d) Let S NC| = iC|=0 4 iC| i C|NC| _ _ . Follow the same method as in parts (a) - (c) to obtain a formula for S NC| in terms of S NC|1 , S NC|2 , ., S C|0 and solve the recurrence. Solving the

13、 recurrence is very difficult. -1- _ _ double RoundUp( double N, int DecPlaces ) int i; double AmountToAdd = 0.5; for( i = 0; i DecPlaces; i+ ) AmountToAdd /= 10; return N + AmountToAdd; void PrintFractionPart( double FractionPart, int DecPlaces ) int i, Adigit; for( i = 0; i DecPlaces; i+ ) Fractio

14、nPart *= 10; ADigit = IntPart( FractionPart ); PrintDigit( Adigit ); FractionPart = DecPart( FractionPart ); void PrintReal( double N, int DecPlaces ) int IntegerPart; double FractionPart; if( N 0 ) putchar(.); PrintFractionPart( FractionPart, DecPlaces ); Fig. 1.1. _ _ 1.7 iC|=C|ClfNC|/ 2C|Crf N i

15、1 _ = iC|=1 N i 1 _ iC|=1 C|ClfNC|/ 2 1C|Crf i 1 _ ln NC| ln NC|/ 2 ln 2. -2- 1.8 2 4 = 16 1 (modC| 5). (2 4 ) 25 1 25 (modC| 5). Thus 2 100 1 (modC| 5). 1.9 (a) Proof is by induction. The statement is clearly true for NC| = 1 and NC| = 2. Assume true for NC| = 1, 2, ., kC|. Then iC|=1 kC|+1 F iC| =

16、 iC|=1 k F iC| +F kC|+1 . By the induction hypothesis, the value of the sum on the right is F kC|+2 2 + F kC|+1 = F kC|+3 2, where the latter equality follows from the definition of the Fibonacci numbers. This proves the claim for NC| = kC| + 1, and hence for all NC|. (b) As in the text, the proof i

17、s by induction. Observe that + 1 = 2 . This implies that 1 + 2 = 1. For NC| = 1 and NC| = 2, the statement is true. Assume the claim is true for NC| = 1, 2, ., kC|. F kC|+1 = F kC| + F kC|1 by the definition and we can use the inductive hypothesis on the right-hand side, obtaining F kC|+1 kC| + kC|1

18、 1 kC|+1 + 2 kC|+1 F kC|+1 ( 1 + 2 ) kC|+1 kC|+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. 1.10 (a) iC|=1 N (2iC|1) = 2 iC|=1 N iC| iC|=1 N 1 = NC|(NC|+1) NC| = N C|2 . (b) The easiest way

19、to prove this is by induction. The case NC| = 1 is trivial. Otherwise, iC|=1 NC|+1 i C|3 = (NC|+1) 3 + iC|=1 N i C|3 = (NC|+1) 3 + 4 N C|2 (NC|+1) 2 _ = (NC|+1) 2 C| Clc Cbv Clf 4 N C|2 _ + (NC|+1)C| Crc Cbv Crf = (NC|+1) 2 C| Clc Cbv Clf 4 N C|2 + 4NC| + 4 _ C| Crc Cbv Crf = 2 2 (NC|+1) 2 (NC|+2) 2

20、 _ = C| Clc Cbv Clf 2 (NC|+1)(NC|+2) _ C| Crc Cbv Crf 2 = C| Clc Cbv Clf iC|=1 NC|+1 iC| Crc Cbv Crf 2 -3- Chapter 2: Algorithm Analysis 2.1 2/NC|, 37, CrnCrn NC|C|, NC|, NC|log log NC|, NC|log NC|, NC|log (N C|2 ), NC|log 2 NC|, N C|1.5 , N C|2 , N C|2 log NC|, N C|3 ,2 NC|/ 2 , 2 NC| . NC|log NC|

21、and NC|log (N C|2 ) grow at the same rate. 2.2 (a) True. (b) False. A counterexample is T C|1 (NC|) = 2NC|, T C|2 (NC|) = NC|, and CfC|C|(NC|) = NC|. (c) False. A counterexample is T C|1 (NC|) = N C|2 , T C|2 (NC|) = NC|, and CfC|C|(NC|) = N C|2 . (d) False. The same counterexample as in part (c) ap

22、plies. 2.3 We claim that NC|log NC| is the slower growing function. To see this, suppose otherwise. Then, N C|/ CrnCrnCrnCrnCrn log NC|C| would grow slower than log NC|. Taking logs of both sides, we find that, under this assumption, / CrnCrnCrnCrnCrnCrn log NC|C|log NC| grows slower than log log NC

23、|. But the first expres- sion simplifies to CrnCrnCrnCrnCrnCrn log NC|C|.IfLC| = log NC|, then we are claiming that CrnCrn LC|C| grows slower than log LC|, or equivalently, that 2 LC| grows slower than log 2 LC|. But we know that log 2 LC| = (LC|), so the original assumption is false, proving the cl

24、aim. 2.4 Clearly, log k C|1 NC| = (log k C|2 NC|)ifk C|1 k C|2 , so we need to worry only about positive integers. The claim is clearly true for kC| = 0 and kC| = 1. Suppose it is true for kC| iC|. Then, by LHospitals rule, NC| lim N log iC| N _ = NC| lim i N log iC|1 N _ The second limit is zero by

25、 the inductive hypothesis, proving the claim. 2.5 Let CfC|C|(NC|) = 1 when NC| is even, and NC| when NC| is odd. Likewise, let gC|(NC|) = 1 when NC| is odd, and NC| when NC| is even. Then the ratio CfC|C|(NC|) / gC|(NC|) oscillates between 0 and . 2.6 For all these programs, the following analysis w

26、ill agree with a simulation: (I) The running time is OC|(NC|). (II) The running time is OC|(N C|2 ). (III) The running time is OC|(N C|3 ). (IV) The running time is OC|(N C|2 ). (V) CjC| can be as large as i C|2 , which could be as large as N C|2 . kC| can be as large as CjC|, which is N C|2 . The r

27、unning time is thus proportional to N C|. N C|2. N C|2 , which is OC|(N C|5 ). (VI) The ifC| statement is executed at most N C|3 times, by previous arguments, but it is true only OC|(N C|2 ) times (because it is true exactly iC| times for each iC|). Thus the innermost loop is only executed OC|(N C|2

28、 ) times. Each time through, it takes OC|(Cj C|2 ) = OC|(N C|2 ) time, for a total of OC|(N C|4 ). This is an example where multiplying loop sizes can occasionally give an overesti- mate. 2.7 (a) It should be clear that all algorithms generate only legal permutations. The first two algorithms have t

29、ests 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 to R. Floyd, is not as obv

30、ious; the correctness can be proved by induction. -4- 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 Swap( Ai, A RandInt( 0, N-1 ) ); then not all permutations are equally likely. To see thi

31、s, notice that for NC| = 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 equally represented. (b) For the first algorithm, the time to

32、decide if a random number to be placed in AC|iC| has not been used earlier is OC|(iC|). The expected number of random numbers that need to be tried is NC|/ (NC| iC|). This is obtained as follows: iC| of the NC| numbers would be duplicates. Thus the probability of success is (NC| iC|) / NC|. Thus the

33、 expected number of independent trials is NC|/ (NC| iC|). The time bound is thus iC|=0 NC|1 NC|i Ni _ iC|=0 NC|1 NC|i N C|2 _ Next; AfterP = P-Next; /* Both P and AfterP assumed not NULL. */ P-Next = AfterP-Next; BeforeP-Next = AfterP; AfterP-Next = P; Fig. 3.2. _ _ (b) For doubly linked lists, the

34、code is shown in Fig. 3.3. _ _ /* P and AfterP are cells to be switched. Error checks as before. */ void SwapWithNext( Position P, List L ) Position BeforeP, AfterP; BeforeP = P-Prev; AfterP = P-Next; P-Next = AfterP-Next; BeforeP-Next = AfterP; AfterP-Next = P; P-Next-Prev = P; P-Prev = AfterP; Aft

35、erP-Prev = BeforeP; Fig. 3.3. _ _ 3.4 IntersectC| is shown on page 9. -8- _ _ /* This code can be made more abstract by using operations such as */ /* Retrieve and IsPastEnd to replace L1Pos-Element and L1Pos != NULL. */ /* We have avoided this because these operations were not rigorously defined. *

36、/ List Intersect( List L1, List L2 ) List Result; Position L1Pos, L2Pos, ResultPos; L1Pos = First( L1 ); L2Pos = First( L2 ); Result = MakeEmpty( NULL ); ResultPos = First( Result ); while( L1Pos != NULL else if( L1Pos-Element L2Pos-Element ) L2Pos = Next( L2Pos, L2 ); else Insert( L1Pos-Element, Re

37、sult, ResultPos ); L1 = Next( L1Pos, L1 ); L2 = Next( L2Pos, L2 ); ResultPos = Next( ResultPos, Result ); return Result; _ _ 3.5 Fig. 3.4 contains the code for Union.C| 3.7 (a) One algorithm is to keep the result in a sorted (by exponent) linked list. Each of the MNC| multiplies requires a search of

38、 the linked list for duplicates. Since the size of the linked list is OC|(MNC|), the total running time is OC|(M C|2 N C|2 ). (b) The bound can be improved by multiplying one term by the entire other polynomial, and then using the equivalent of the procedure in Exercise 3.2 to insert the entire sequ

39、ence. Then each sequence takes OC|(MNC|), but there are only MC| of them, giving a time bound of OC|(M C|2 NC|). (c) An OC|(MNC|log MNC|) solution is possible by computing all MNC| pairs and then sorting by exponent using any algorithm in Chapter 7. It is then easy to merge duplicates afterward. (d)

40、 The choice of algorithm depends on the relative values of MC| and NC|. If they are close, then the solution in part (c) is better. If one polynomial is very small, then the solution in part (b) is better. -9- _ _ List Union( List L1, List L2 ) List Result; ElementType InsertElement; Position L1Pos,

41、 L2Pos, ResultPos; L1Pos = First( L1 ); L2Pos = First( L2 ); Result = MakeEmpty( NULL ); ResultPos = First( Result ); while ( L1Pos != NULL L1Pos = Next( L1Pos, L1 ); else if( L1Pos-Element L2Pos-Element ) InsertElement = L2Pos-Element; L2Pos = Next( L2Pos, L2 ); else InsertElement = L1Pos-Element;

42、L1Pos = Next( L1Pos, L1 ); L2Pos = Next( L2Pos, L2 ); Insert( InsertElement, Result, ResultPos ); ResultPos = Next( ResultPos, Result ); /* Flush out remaining list */ while( L1Pos != NULL ) Insert( L1Pos-Element, Result, ResultPos ); L1Pos = Next( L1Pos, L1 ); ResultPos = Next( ResultPos, Result );

43、 while( L2Pos != NULL ) Insert( L2Pos-Element, Result, ResultPos ); L2Pos = Next( L2Pos, L2 ); ResultPos = Next( ResultPos, Result ); return Result; Fig. 3.4. _ _ 3.8 One can use the PowC| function in Chapter 2, adapted for polynomial multiplication. If PC| is small, a standard method that uses OC|(

44、PC|) multiplies instead of OC|(log PC|) might be better because the multiplies would involve a large number with a small number, which is good for the multiplication routine in part (b). 3.10 This is a standard programming project. The algorithm can be sped up by setting MC| = MC| modC| NC|, so that

45、 the hot potato never goes around the circle more than once, and -10- then if MC| NC|/ 2, passing the potato appropriately in the alternative direction. This requires a doubly linked list. The worst-case running time is clearly OC|(NC| minC|(MC|, NC|), although when these heuristics are used, and MC

46、| and NC| are comparable, the algorithm might be significantly faster. If MC| = 1, the algorithm is clearly linear. The VAX/VMS C compilers memory management routines do poorly with the particular pattern of CfreeC|sin this case, causing OC|(NC|log NC|) behavior. 3.12 Reversal of a singly linked lis

47、t can be done nonrecursively by using a stack, but this requires OC|(NC|) extra space. The solution in Fig. 3.5 is similar to strategies employed in gar- bage collection algorithms. At the top of the whileC| loop, the list from the start to Pre- viousPosC| is already reversed, whereas the rest of the list, from CurrentPosC| to the end, is n