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

DataStructuresandAlgorithmAnalysisinC(secondedition)SolutionsManualMarkAllenWeissFloridaInternationalUniversityPrefaceIncludedinthismanualareanswerstomostoftheexercisesinthetextbookDataStructuresandAlgorithmAnalysisinC,secondedition,publishedbyAddison-Wesley.Theseanswersreflectthestateofthebookinthefirstprinting.Specificallyomittedarelikelyprogrammingassignmentsandanyquestionwhosesolu-tionispointedtobyareferenceattheendofthechapter.Solutionsvaryindegreeofcomplete-ness;generally,minordetailsarelefttothereader.Forclarity,programsaremeanttobepseudo-Cratherthancompletelyperfectcode.Errorscanbereportedtoweiss@fiu.edu.ThankstoGrigoriSchwarzandBrianHarveyforpointingouterrorsinpreviousincarnationsofthismanual.TableofContents1.Chapter1:Introduction......................................................................................................12.Chapter2:AlgorithmAnalysis..........................................................................................43.Chapter3:Lists,Stacks,andQueues.................................................................................74.Chapter4:Trees.................................................................................................................145.Chapter5:Hashing............................................................................................................256.Chapter6:PriorityQueues(Heaps)...................................................................................297.Chapter7:Sorting..............................................................................................................368.Chapter8:TheDisjointSetADT.......................................................................................429.Chapter9:GraphAlgorithms.............................................................................................4510.Chapter10:AlgorithmDesignTechniques......................................................................5411.Chapter11:AmortizedAnalysis......................................................................................6312.Chapter12:AdvancedDataStructuresandImplementation............................................66-iii-Chapter1:Introduction1.3Becauseofround-offerrors,itiscustomarytospecifythenumberofdecimalplacesthatshouldbeincludedintheoutputandroundupaccordingly.Otherwise,numberscomeoutlookingstrange.Weassumeerrorcheckshavealreadybeenperformed;theroutineSeparateOislefttothereader.CodeisshowninFig.1.1.1.4ThegeneralwaytodothisistowriteaprocedurewithheadingvoidProcessFile(constchar*FileName);whichopensFileName,Odoeswhateverprocessingisneeded,andthenclosesit.Ifalineoftheform#includeSomeFileisdetected,thenthecallProcessFile(SomeFile);ismaderecursively.Self-referentialincludescanbedetectedbykeepingalistoffilesforwhichacalltoProcessFileOhasnotyetterminated,andcheckingthislistbeforemakinganewcalltoProcessFile.O1.5(a)Theproofisbyinduction.Thetheoremisclearlytruefor0<XO≤1,sinceitistrueforXO=1,andforXO<1,logXOisnegative.Itisalsoeasytoseethatthetheoremholdsfor1<XO≤2,sinceitistrueforXO=2,andforXO<2,logXOisatmost1.SupposethetheoremistrueforpO<XO≤2pO(wherepOisapositiveinteger),andconsiderany2pO<YO≤4pO(pO≥1).ThenlogYO=1+log(YO/2)<1+YO/2<YO/2+YO/2≤YO,wherethefirstine-qualityfollowsbytheinductivehypothesis.(b)Let2XO=AO.ThenAOBO=(2XO)BO=2XBO.ThuslogAOBO=XBO.SinceXO=logAO,thetheoremisproved.1.6(a)Thesumis4/3andfollowsdirectlyfromtheformula.(b)SO=41__+422___+433___+....4SO=1+42__+423___+....Subtractingthefirstequationfromthesecondgives3SO=1+41__+422___+....Bypart(a),3SO=4/3soSO=4/9.(c)SO=41__+424___+439___+....4SO=1+44__+429___+4316___+....Subtractingthefirstequa-tionfromthesecondgives3SO=1+43__+425___+437___+....Rewriting,weget3SO=2iO=0Σ∞4iOi___+iO=0Σ∞4iO1___.Thus3SO=2(4/9)+4/3=20/9.ThusSO=20/27.(d)LetSNO=iO=0Σ∞4iOiONO___.Followthesamemethodasinparts(a)-(c)toobtainaformulaforSNOintermsofSNO−1,SNO−2,...,SO0andsolvetherecurrence.Solvingtherecurrenceisverydifficult.-1-______________________________________________________________________________________________________________________________________________________________doubleRoundUp(doubleN,intDecPlaces){inti;doubleAmountToAdd=0.5;for(i=0;i<DecPlaces;i++)AmountToAdd/=10;returnN+AmountToAdd;}voidPrintFractionPart(doubleFractionPart,intDecPlaces){inti,Adigit;for(i=0;i<DecPlaces;i++){FractionPart*=10;ADigit=IntPart(FractionPart);PrintDigit(Adigit);FractionPart=DecPart(FractionPart);}}voidPrintReal(doubleN,intDecPlaces){intIntegerPart;doubleFractionPart;if(N<0){putchar(’-’);N=-N;}N=RoundUp(N,DecPlaces);IntegerPart=IntPart(N);FractionPart=DecPart(N);PrintOut(IntegerPart);/*Usingroutineintext*/if(DecPlaces>0)putchar(’.’);PrintFractionPart(FractionPart,DecPlaces);}Fig.1.1.______________________________________________________________________________________________________________________________________________________________1.7iO=OINO/2OKΣNi1__=iO=1ΣNi1__−iO=1ΣOINO/2−1OKi1__∼∼lnNO−lnNO/2∼∼ln2.-2-1.824=16≡1(modO5).(24)25≡125(modO5).Thus2100≡1(modO5).1.9(a)Proofisbyinduction.ThestatementisclearlytrueforNO=1andNO=2.AssumetrueforNO=1,2,...,kO.TheniO=1ΣkO+1FiO=iO=1ΣkFiO+FkO+1.Bytheinductionhypothesis,thevalueofthesumontherightisFkO+2−2+FkO+1=FkO+3−2,wherethelatterequalityfollowsfromthedefinitionoftheFibonaccinumbers.ThisprovestheclaimforNO=kO+1,andhenceforallNO.(b)Asinthetext,theproofisbyinduction.Observethatφ+1=φ2.Thisimpliesthatφ−1+φ−2=1.ForNO=1andNO=2,thestatementistrue.AssumetheclaimistrueforNO=1,2,...,kO.FkO+1=FkO+FkO−1bythedefinitionandwecanusetheinductivehypothesisontheright-handside,obtainingFkO+1<φkO+φkO−1<φ−1φkO+1+φ−2φkO+1FkO+1<(φ−1+φ−2)φkO+1<φkO+1andprovingthetheorem.(c)Seeanyoftheadvancedmathreferencesattheendofthechapter.Thederivationinvolvestheuseofgeneratingfunctions.1.10(a)iO=1ΣN(2iO−1)=2iO=1ΣNiO−iO=1ΣN1=NO(NO+1)−NO=NO2.(b)Theeasiestwaytoprovethisisbyinduction.ThecaseNO=1istrivial.Otherwise,iO=1ΣNO+1iO3=(NO+1)3+iO=1ΣNiO3=(NO+1)3+4NO2(NO+1)2_________=(NO+1)2OHAI4NO2___+(NO+1)OJAK=(NO+1)2OHAI4NO2+4NO+4___________OJAK=22(NO+1)2(NO+2)2_____________=OHAI2(NO+1)(NO+2)___________OJAK2=OHAIiO=1ΣNO+1iOJAK2-3-Chapter2:AlgorithmAnalysis2.12/NO,37,√MMNOO,NO,NOloglogNO,NOlogNO,NOlog(NO2),NOlog2NO,NO1.5,NO2,NO2logNO,NO3,2NO/2,2NO.NOlogNOandNOlog(NO2)growatthesamerate.2.2(a)True.(b)False.AcounterexampleisTO1(NO)=2NO,TO2(NO)=NO,andPfOO(NO)=NO.(c)False.AcounterexampleisTO1(NO)=NO2,TO2(NO)=NO,andPfOO(NO)=NO2.(d)False.Thesamecounterexampleasinpart(c)applies.2.3WeclaimthatNOlogNOistheslowergrowingfunction.Toseethis,supposeotherwise.Then,NOε/√MMMMMlogNOOwouldgrowslowerthanlogNO.Takinglogsofbothsides,wefindthat,underthisassumption,ε/√MMMMMMlogNOOlogNOgrowsslowerthanloglogNO.Butthefirstexpres-sionsimplifiestoε√MMMMMMlogNOO.IfLO=logNO,thenweareclaimingthatε√MMLOOgrowsslowerthanlogLO,orequivalently,thatε2LOgrowsslowerthanlog2LO.Butweknowthatlog2LO=ο(LO),sotheoriginalassumptionisfalse,provingtheclaim.2.4Clearly,logkO1NO=ο(logkO2NO)ifkO1<kO2,soweneedtoworryonlyaboutpositiveintegers.TheclaimisclearlytrueforkO=0andkO=1.SupposeitistrueforkO<iO.Then,byL’Hospital’srule,NO→∞limNlogiON______=NO→∞limiNlogiO−1N_______Thesecondlimitiszerobytheinductivehypothesis,provingtheclaim.2.5LetPfOO(NO)=1whenNOiseven,andNOwhenNOisodd.Likewise,letgO(NO)=1whenNOisodd,andNOwhenNOiseven.ThentheratioPfOO(NO)/gO(NO)oscillatesbetween0and∞.2.6Foralltheseprograms,thefollowinganalysiswillagreewithasimulation:(I)TherunningtimeisOO(NO).(II)TherunningtimeisOO(NO2).(III)TherunningtimeisOO(NO3).(IV)TherunningtimeisOO(NO2).(V)PjOcanbeaslargeasiO2,whichcouldbeaslargeasNO2.kOcanbeaslargeasPjO,whichisNO2.TherunningtimeisthusproportionaltoNO.NO2.NO2,whichisOO(NO5).(VI)TheifOstatementisexecutedatmostNO3times,bypreviousarguments,butitistrueonlyOO(NO2)times(becauseitistrueexactlyiOtimesforeachiO).ThustheinnermostloopisonlyexecutedOO(NO2)times.Eachtimethrough,ittakesOO(PjO2)=OO(NO2)time,foratotalofOO(NO4).Thisisanexamplewheremultiplyingloopsizescanoccasionallygiveanoveresti-mate.2.7(a)Itshouldbeclearthatallalgorithmsgenerateonlylegalpermutations.Thefirsttwoalgorithmshaveteststoguaranteenoduplicates;thethirdalgorithmworksbyshufflinganarraythatinitiallyhasnoduplicates,sononecanoccur.Itisalsoclearthatthefirsttwoalgorithmsarecompletelyrandom,andthateachpermutationisequallylikely.Thethirdalgorithm,duetoR.Floyd,isnotasobvious;thecorrectnesscanbeprovedbyinduction.-4-SeeJ.Bentley,"ProgrammingPearls,"CommunicationsoftheACM30(1987),754-757.Notethatifthesecondlineofalgorithm3isreplacedwiththestatementSwap(A[i],A[RandInt(0,N-1)]);thennotallpermutationsareequallylikely.Toseethis,noticethatforNO=3,thereare27equallylikelywaysofperformingthethreeswaps,dependingonthethreerandomintegers.Sincethereareonly6permutations,and6doesnotevenlydivide27,eachpermutationcannotpossiblybeequallyrepresented.(b)Forthefirstalgorithm,thetimetodecideifarandomnumbertobeplacedinAO[iO]hasnotbeenusedearlierisOO(iO).TheexpectednumberofrandomnumbersthatneedtobetriedisNO/(NO−iO).Thisisobtainedasfollows:iOoftheNOnumberswouldbeduplicates.Thustheprobabilityofsuccessis(NO−iO)/NO.ThustheexpectednumberofindependenttrialsisNO/(NO−iO).ThetimeboundisthusiO=0ΣNO−1NO−iNi____<iO=0ΣNO−1NO−iNO2____<NO2iO=0ΣNO−1NO−i1____<NO2PjO=1ΣNPj1__=OO(NO2logNO)ThesecondalgorithmsavesafactorofiOforeachrandomnumber,andthusreducesthetimeboundtoOO(NOlogNO)onaverage.Thethirdalgorithmisclearlylinear.(c,d)Therunningtimesshouldagreewiththeprecedinganalysisifthemachinehasenoughmemory.Ifnot,thethirdalgorithmwillnotseemlinearbecauseofadrasticincreaseforlargeNO.(e)Theworst-caserunningtimeofalgorithmsIandIIcannotbeboundedbecausethereisalwaysafiniteprobabilitythattheprogramwillnotterminatebysomegiventimeTO.Thealgorithmdoes,however,terminatewithprobability1.Theworst-caserunningtimeofthethirdalgorithmislinear-itsrunningtimedoesnotdependonthesequenceofrandomnumbers.2.8Algorithm1wouldtakeabout5daysforNO=10,000,14.2yearsforNO=100,000and140centuriesforNO=1,000,000.Algorithm2wouldtakeabout3hoursforNO=100,000andabout2weeksforNO=1,000,000.Algorithm3woulduse1⁄12minutesforNO=1,000,000.Thesecalculationsassumeamachinewithenoughmemorytoholdthearray.Algorithm4solvesaproblemofsize1,000,000in3seconds.2.9(a)OO(NO2).(b)OO(NOlogNO).2.10(c)Thealgorithmislinear.2.11UseavariationofbinarysearchtogetanOO(logNO)solution(assumingthearrayispreread).2.13(a)TesttoseeifNOisanoddnumber(or2)andisnotdivisibleby3,5,7,...,√MMNOO.(b)OO(√MMNOO),assumingthatalldivisionscountforoneunitoftime.(c)BO=OO(logNO).(d)OO(2BO/2).(e)Ifa20-bitnumbercanbetestedintimeTO,thena40-bitnumberwouldrequireaboutTO2time.(f)BOisthebettermeasurebecauseitmoreaccuratelyrepresentsthesizeOoftheinput.-5-2.14TherunningtimeisproportionaltoNOtimesthesumofthereciprocalsoftheprimeslessthanNO.ThisisOO(NOloglogNO).SeeKnuth,Volume2,page394.2.15ComputeXO2,XO4,XO8,XO10,XO20,XO40,XO60,andXO62.2.16MaintainanarrayPowersOfXOthatcanbefilledinaforloop.ThearraywillcontainXO,XO2,XO4,uptoXO2OIlogNOK.ThebinaryrepresentationofNO(whichcanbeobtainedbytestingevenoroddandthendividingby2,untilallbitsareexamined)canbeusedtomultiplytheappropriateentriesofthearray.2.17ForNO=0orNO=1,thenumberofmultipliesiszero.IfbO(NO)isthenumberofonesinthebinaryrepresentationofNO,thenifNO>1,thenumberofmultipliesusedisOIlogNOK+bO(NO)−12.18(a)AO.(b)BO.(c)Theinformationgivenisnotsufficienttodetermineananswer.Wehaveonlyworst-casebounds.(d)Yes.2.19(a)Recursionisunnecessaryiftherearetwoorfewerelements.(b)OnewaytodothisistonotethatifthefirstNO−1elementshaveamajority,thenthelastelementcannotchangethis.Otherwise,thelastelementcouldbeamajority.ThusifNOisodd,ignorethelastelement.Runthealgorithmasbefore.Ifnomajorityelementemerges,thenreturntheNOthOelementasacandidate.(c)TherunningtimeisOO(NO),andsatisfiesTO(NO)=TO(NO/2)+OO(NO).(d)Onecopyoftheoriginalneedstobesaved.Afterthis,theBOarray,andindeedtherecur-sioncanbeavoidedbyplacingeachBiOintheAOarray.ThedifferenceisthattheoriginalrecursivestrategyimpliesthatOO(logNO)arraysareused;thisguaranteesonlytwocopies.2.20Otherwise,wecouldperformoperationsinparallelbycleverlyencodingseveralintegersintoone.Forinstance,ifA=001,B=101,C=111,D=100,wecouldaddAandBatthesametimeasCandDbyadding00A00C+00B00D.WecouldextendthistoaddNOpairsofnumbersatonceinunitcost.2.22No.IfLowO=1,HighO=2,thenMidO=1,andtherecursivecalldoesnotmakeprogress.2.24No.AsinExercise2.22,noprogressismade.-6-Chapter3:Lists,Stacks,andQueues3.2ThecommentsforExercise3.4regardingtheamountofabstractnessusedapplyhere.TherunningtimeoftheprocedureinFig.3.1isOO(LO+PO).______________________________________________________________________________________________________________________________________________________________voidPrintLots(ListL,ListP){intCounter;PositionLpos,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)Forsinglylinkedlists,thecodeisshowninFig.3.2.-7-______________________________________________________________________________________________________________________________________________________________/*BeforePisthecellbeforethetwoadjacentcellsthataretobeswapped.*//*Errorchecksareomittedforclarity.*/voidSwapWithNext(PositionBeforeP,ListL){PositionP,AfterP;P=BeforeP->Next;AfterP=P->Next;/*BothPandAfterPassumednotNULL.*/P->Next=AfterP->Next;BeforeP->Next=AfterP;AfterP->Next=P;}Fig.3.2.______________________________________________________________________________________________________________________________________________________________(b)Fordoublylinkedlists,thecodeisshowninFig.3.3.______________________________________________________________________________________________________________________________________________________________/*PandAfterParecellstobeswitched.Errorchecksasbefore.*/voidSwapWithNext(PositionP,ListL){PositionBeforeP,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.4IntersectOisshownonpage9.-8-______________________________________________________________________________________________________________________________________________________________/*Thiscodecanbemademoreabstractbyusingoperationssuchas*//*RetrieveandIsPastEndtoreplaceL1Pos->ElementandL1Pos!=NULL.*//*Wehaveavoidedthisbecausetheseoperationswerenotrigorouslydefined.*/ListIntersect(ListL1,ListL2){ListResult;PositionL1Pos,L2Pos,ResultPos;L1Pos=First(L1);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);while(L1Pos!=NULL&&L2Pos!=NULL){if(L1Pos->Element<L2Pos->Element)L1Pos=Next(L1Pos,L1);elseif(L1Pos->Element>L2Pos->Element)L2Pos=Next(L2Pos,L2);else{Insert(L1Pos->Element,Result,ResultPos);L1=Next(L1Pos,L1);L2=Next(L2Pos,L2);ResultPos=Next(ResultPos,Result);}}returnResult;}______________________________________________________________________________________________________________________________________________________________3.5Fig.3.4containsthecodeforUnion.O3.7(a)Onealgorithmistokeeptheresultinasorted(byexponent)linkedlist.EachoftheMNOmultipliesrequiresasearchofthelinkedlistforduplicates.SincethesizeofthelinkedlistisOO(MNO),thetotalrunningtimeisOO(MO2NO2).(b)Theboundcanbeimprovedbymultiplyingonetermbytheentireotherpolynomial,andthenusingtheequivalentoftheprocedureinExercise3.2toinserttheentiresequence.TheneachsequencetakesOO(MNO),butthereareonlyMOofthem,givingatimeboundofOO(MO2NO).(c)AnOO(MNOlogMNO)solutionispossiblebycomputingallMNOpairsandthensortingbyexponentusinganyalgorithminChapter7.Itistheneasytomergeduplicatesafterward.(d)ThechoiceofalgorithmdependsontherelativevaluesofMOandNO.Iftheyareclose,thenthesolutioninpart(c)isbetter.Ifonepolynomialisverysmall,thenthesolutioninpart(b)isbetter.-9-______________________________________________________________________________________________________________________________________________________________ListUnion(ListL1,ListL2){ListResult;ElementTypeInsertElement;PositionL1Pos,L2Pos,ResultPos;L1Pos=First(L1);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);while(L1Pos!=NULL&&L2Pos!=NULL){if(L1Pos->Element<L2Pos->Element){InsertElement=L1Pos->Element;L1Pos=Next(L1Pos,L1);}elseif(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);}/*Flushoutremaininglist*/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);}returnResult;}Fig.3.4.______________________________________________________________________________________________________________________________________________________________3.8OnecanusethePowOfunctioninChapter2,adaptedforpolynomialmultiplication.IfPOissmall,astandardmethodthatusesOO(PO)multipliesinsteadofOO(logPO)mightbebetterbecausethemultiplieswouldinvolvealargenumberwithasmallnumber,whichisgoodforthemultiplicationroutineinpart(b).3.10Thisisastandardprogrammingproject.ThealgorithmcanbespedupbysettingM'O=MOmodONO,sothatthehotpotatonevergoesaroundthecirclemorethanonce,and-10-thenifM'O>NO/2,passingthepotatoappropriatelyinthealternativedirection.Thisrequiresadoublylinkedlist.Theworst-caserunningtimeisclearlyOO(NOminO(MO,NO)),althoughwhentheseheuristicsareused,andMOandNOarecomparable,thealgorithmmightbesignificantlyfaster.IfMO=1,thealgorithmisclearlylinear.TheVAX/VMSCcompiler’smemorymanagementroutinesdopoorlywiththeparticularpatternofPfreeOsinthiscase,causingOO(NOlogNO)behavior.3.12Reversalofasinglylinkedlistcanbedonenonrecursivelybyusingastack,butthisrequiresOO(NO)extraspace.ThesolutioninFig.3.5issimilartostrategiesemployedingar-bagecollectionalgorithms.AtthetopofthewhileOloop,thelistfromthestarttoPre-viousPosOisalreadyreversed,whereastherestofthelist,fromCurrentPosOtotheend,isnormal.Thisalgorithmusesonlyconstantextraspace.______________________________________________________________________________________________________________________________________________________________/*AssumingnoheaderandLisnotempty.*/ListReverseList(ListL){PositionCurrentPos,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;returnCurrentPos;}Fig.3.5.______________________________________________________________________________________________________________________________________________________________3.15(a)ThecodeisshowninFig.3.6.(b)SeeFig.3.7.(c)Thisfollowsfromwell-knownstatisticaltheorems.SeeSleatorandTarjan’spaperintheChapter11references.3.16(c)DeleteOtakesOO(NO)andisintwonestedforloopseachofsizeNO,givinganobviousOO(NO3)bound.AbetterboundofOO(NO2)isobtainedbynotingthatonlyNOelementscanbedeletedfromalistofsizeNO,h