数据结构与算法分析+习题答案.pdf

Data StructuresandAlgorithm Analysis in C(second edition)Solutions ManualMark Allen WeissFlorida 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 answers 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 clarity,programs are meant to bepseudo-C rather than completely perfect code.Errors can be reported to weissfiu.edu.Thanks to Grigori Schwarz and Brian Harveyfor pointing out errors in previous incarnations of this manual.Table of Contents1.Chapter 1:Introduction.12.Chapter 2:Algorithm Analysis.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:Amortized 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 thatshould be included in the output and round up accordingly.Otherwise,numbers come outlooking strange.We assume error checks have already been performed;the routineSeparate?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 then closes it.If a line ofthe form#include SomeFileis detected,then the callProcessFile(SomeFile);is made recursively.Self-referential includes can be detected by keeping a list of files forwhich a call to ProcessFile?has not yet terminated,and checking this list before making anew call to ProcessFile.?1.5(a)The proof is by induction.The theorem is clearly true for 0 X?1,since it is true forX?=1,and for X?1,log X?is negative.It is also easy to see that the theorem holds for1 X?2,since it is true for X?=2,and for X?2,log X?is at most 1.Suppose the theoremis 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 ine-quality follows by the inductive hypothesis.(b)Let 2X?=A?.Then A?B?=(2X?)B?=2XB?.Thus log A?B?=XB?.Since X?=log A?,thetheorem is proved.1.6(a)The sum is 4/3 and follows directly from the formula.(b)S?=41_+422_ _+433_ _+.4S?=1+42_ _+423_ _+.Subtracting the first equation fromthe second gives 3S?=1+41 _+422_ _+.By part(a),3S?=4/3 so S?=4/9.(c)S?=41_+424_ _+439_ _+.4S?=1+44 _ _+429_ _+4316_ _+.Subtracting the first equa-tionfromthesecondgives3S?=1+43_ _+425_ _+437_ _+.Rewriting,weget3S?=2i?=04i?i_ _+i?=04i?1_ _.Thus 3S?=2(4/9)+4/3=20/9.Thus S?=20/27.(d)Let SN?=i?=04i?i?N?_.Follow the same method as in parts(a)-(c)to obtain a formula for SN?in terms of SN?1,SN?2,.,S?0and solve the recurrence.Solving the recurrence is verydifficult.-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+)FractionPart*=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.7i?=?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(a)Proof is by induction.The statement is clearly true for N?=1 and N?=2.Assume truefor N?=1,2,.,k?.Theni?=1k?+1Fi?=i?=1kFi?+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 Fibonacci numbers.This proves the claim for N?=k?+1,and hence for allN?.(b)As in the text,the proof is by induction.Observe that +1=2.This implies that1+2=1.For N?=1 and N?=2,the statement is true.Assume the claim is true forN?=1,2,.,k?.Fk?+1=Fk?+Fk?1by the definition and we can use the inductive hypothesis on the right-hand side,obtainingFk?+1 k?+k?1 1k?+1+2k?+1Fk?+1 (1+2)k?+1 k?+1and proving the theorem.(c)See any of the advanced math references at the end of the chapter.The derivationinvolves the use of generating functions.1.10(a)i?=1N(2i?1)=2i?=1Ni?i?=1N1=N?(N?+1)N?=N?2.(b)The easiest way to prove this is by induction.The case N?=1 is trivial.Otherwise,i?=1N?+1i?3=(N?+1)3+i?=1Ni?3=(N?+1)3+4N?2(N?+1)2_=(N?+1)2?4N?2_+(N?+1)?=(N?+1)2?4N?2+4N?+4_?=22(N?+1)2(N?+2)2_ _=?2(N?+1)(N?+2)_?2=?i?=1N?+1i?2-3-Chapter 2:Algorithm Analysis2.12/N?,37,?N?,N?,N?log log N?,N?log N?,N?log(N?2),N?log2N?,N?1.5,N?2,N?2log N?,N?3,2N?/2,2N?.N?log N?and N?log(N?2)grow at the same rate.2.2(a)True.(b)False.A counterexample is T?1(N?)=2N?,T?2(N?)=N?,and?f?(N?)=N?.(c)False.A counterexample is T?1(N?)=N?2,T?2(N?)=N?,and?f?(N?)=N?2.(d)False.The same counterexample as in part(c)applies.2.3We claim that N?log N?is the slower growing function.To see this,suppose otherwise.Then,N?/?log N?would grow slower than log N?.Taking logs of both sides,we find that,under this assumption,/?log N?log N?grows slower than log log N?.But the first expres-sion simplifies to?log N?.If L?=log N?,then we are claiming that?L?grows slower thanlog L?,or equivalently,that 2L?grows slower than log2 L?.But we know thatlog2 L?=(L?),so the original assumption is false,proving the claim.2.4Clearly,logk?1N?=(logk?2N?)if k?1 k?2,so we need to worry only about positive integers.The claim is clearly true for k?=0 and k?=1.Suppose it is true for k?i?.Then,byLHospitals rule,N?limNlogi?N_ _=N?lim iNlogi?1N_The second limit is zero by the inductive hypothesis,proving the claim.2.5Let?f?(N?)=1 when N?is even,and N?when N?is odd.Likewise,let g?(N?)=1 when N?isodd,and N?when N?is even.Then the ratio?f?(N?)/g?(N?)oscillates between 0 and.2.6For all these programs,the following analysis will agree with a simulation:(I)The running time is O?(N?).(II)The running time is O?(N?2).(III)The running time is O?(N?3).(IV)The running time is O?(N?2).(V)?j?can be as large as i?2,which could be as large as N?2.k?can be as large as?j?,which isN?2.The running time is thus proportional to N?.N?2.N?2,which is O?(N?5).(VI)The if?statement is executed at most N?3times,by previous arguments,but it is trueonly O?(N?2)times(because it is true exactly i?times for each i?).Thus the innermost loop isonly executed O?(N?2)times.Each time through,it takes O?(?j?2)=O?(N?2)time,for a total ofO?(N?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 twoalgorithms have tests to guarantee no duplicates;the third algorithm works by shuffling anarray that initially has no duplicates,so none can occur.It is also clear that the first twoalgorithms are completely random,and that each permutation is equally likely.The thirdalgorithm,due to R.Floyd,is not as obvious;the correctness can be proved by induction.-4-SeeJ.Bentley,Programming Pearls,Communications of the ACM 30(1987),754-757.Note that if the second line of algorithm 3 is replaced with the statementSwap(Ai,A RandInt(0,N-1);then not all permutations are equally likely.To see this,notice that for N?=3,there are 27equally likely ways of performing the three swaps,depending on the three random integers.Since there are only 6 permutations,and 6 does not evenly divide27,each permutation cannot possibly be equally represented.(b)For the first algorithm,the time to decide if a random number to be placed in A?i?hasnot been used earlier is O?(i?).The expected number of random numbers that need to betried is N?/(N?i?).This is obtained as follows:i?of the N?numbers would be duplicates.Thus the probability of success is(N?i?)/N?.Thus the expected number of independenttrials is N?/(N?i?).The time bound is thusi?=0N?1N?iNi_ i?=0N?1N?iN?2_ N?2i?=0N?1N?i1_ 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 if 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 lastelement cannot change this.Otherwise,the last element could be a majority.Thus if N?isodd,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)One copy of the original needs to be saved.After this,the B?array,and indeed the recur-sion can be avoided by placing each Bi?in the A?array.The difference is that the originalrecursive 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 integersinto one.For instance,if A=001,B=101,C=111,D=100,we could add A and B at thesame time as C and D by adding 00A00C+00B00D.We could extend this to add N?pairsof 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 Queues3.2The comments for Exercise 3.4 regarding the amount of abstractness used apply here.Therunning time of the procedure in Fig.3.1 is O?(L?+P?)._ _ _voidPrintLots(List L,List P)int Counter;Position Lpos,Ppos;Lpos=First(L);Ppos=First(P);Counter=1;while(Lpos!=NULL&Ppos!=NULL)if(Ppos-Element=Counter+)printf(%?,Lpos-Element);Ppos=Next(Ppos,P);Lpos=Next(Lpos,L);Fig.3.1._ _ _3.3(a)For singly linked lists,the code is shown in Fig.3.2.-7-_ _ _/*BeforeP is the cell before the two adjacent cells that are to be swapped.*/*Error checks are omitted for clarity.*/voidSwapWithNext(Position BeforeP,List L)Position P,AfterP;P=BeforeP-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 code is shown in Fig.3.3._ _ _/*P and AfterP are cells to be switched.Error checks as before.*/voidSwapWithNext(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;AfterP-Prev=BeforeP;Fig.3.3._ _ _3.4Intersect?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.*/ListIntersect(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&L2Pos!=NULL)if(L1Pos-Element Element)L1Pos=Next(L1Pos,L1);else if(L1Pos-Element L2Pos-Element)L2Pos=Next(L2Pos,L2);elseInsert(L1Pos-Element,Result,ResultPos);L1=Next(L1Pos,L1);L2=Next(L2Pos,L2);ResultPos=Next(ResultPos,Result);return Result;_ _ _3.5Fig.3.4 contains the code for Union.?3.7(a)One algorithm is to keep the result in a sorted(by exponent)linked list.Each of the MN?multiplies requires a search of the linked list for duplicates.Since the size of the linked listis O?(MN?),the total running time is O?(M?2N?2).(b)The bound can be improved by multiplying one term by the entire other polynomial,andthen using the equivalent of the procedure in Exercise 3.2 to insert the entire sequence.Then each sequence takes O?(MN?),but there are only M?of them,giving a time bound ofO?(M?2N?).(c)An O?(MN?log MN?)solution is possible by computing all MN?pairs and then sorting byexponent using any algorithm in Chapter 7.It is then easy to merge duplicates afterward.(d)The choice of algorithm depends on the relative values of M?and N?.If they are close,then the solution in part(c)is better.If one polynomial is very small,then the solution inpart(b)is better.-9-_ _ _ListUnion(List L1,List L2)List Result;ElementType InsertElement;Position L1Pos,L2Pos,ResultPos;L1Pos=First(L1);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);while(L1Pos!=NULL&L2Pos!=NULL)if(L1Pos-Element Element)InsertElement=L1Pos-Element;L1Pos=Next(L1Pos,L1);else if(L1Pos-Element L2Pos-Element)InsertElement=L2Pos-Element;L2Pos=Next(L2Pos,L2);else InsertElement=L1Pos-Element;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);while(L2Pos!=NULL)Insert(L2Pos-Element,Result,ResultPos);L2Pos=Next(L2Pos,L2);ResultPos=Next(ResultPos,Result);return Result;Fig.3.4._ _ _3.8One can use the Pow?function in Chapter 2,adapted for polynomial multiplication.If P?issmall,a standard method that uses O?(P?)multiplies instead of O?(log P?)might be betterbecause the multiplies would involve a large number with a small number,which is goodfor the multiplication routine in part(b).3.10 This is a standard programming project.The algorithm can be sped up by settingM?=M?mod?N?,so that the hot potato never goes around the circle more than once,and-10-then if M?N?/2,passing the potato appropriately in the alternative direction.Thisrequires a doubly linked list.The worst-case running time is clearly O?(N?min?(M?,N?),although when these heuristics are used,and M?and N?are comparable,the algorithm mightbe significantly faster.If M?=1,the algorithm is clearly linear.The VAX/VMS Ccompilers memory management routines do poorly with the particular pattern of?free?s inthis case,causing O?(N?log N?)behavior.3.12 Reversal of a singly linked list can be done nonrecursively by using a stack,but thisrequires O?(N?)extra space.The solution in Fig.3.5 is similar to strategies employed in gar-bage collection algorithms.At the top of the while?loop,the list from the start to Pre-viousPos?is already reversed,whereas the rest of the list,from CurrentPos?to the end,isnormal.This algorithm uses only constant extra space._ _ _/*Assuming no header and L is not empty.*/ListReverseList(List L)Position CurrentPos,NextPos,PreviousPos;PreviousPos=NULL;CurrentPos=L;NextPos=L-Next;while(NextPos!=NULL)CurrentPos-Next=PreviousPos;PreviousPos=CurrentPos;CurrentPos=NextPos;NextPos=NextPos-Next;CurrentPos-Next=PreviousPos;return CurrentPos;Fig.3.5._ _ _3.15(a)The code is shown in Fig.3.6.(b)See Fig.3.7.(c)This follows from well-known statistical theorems.See Sleator and Tarjans paper inthe Chapter 11 references.3.16(c)Delete?takes O?(N?)and is in two nested for loops each of size N?,giving an obviousO?(N?3)bound.A better bound of O?(N?2)is obtained by noting